【Codeforces】#345 Div1

1. Watchmen
1.1 题目描述
给$n$个点，求曼哈顿距离等于欧式距离的点对数。

1.2 基本思路
由$|x_i-x_j|+|y_i-yj| = sqrt{(x_i-x_j)^2+(y_i-yj)^2}$可以推出$x_i=x_j$或者$y_i=y_j$。
所以变得超级简单了，排序后对两种情况分别累加即可。

1.3 代码

 1 /* A */
 2 #include <iostream>
 3 #include <sstream>
 4 #include <string>
 5 #include <map>
 6 #include <queue>
 7 #include <set>
 8 #include <stack>
 9 #include <vector>
10 #include <deque>
11 #include <bitset>
12 #include <algorithm>
13 #include <cstdio>
14 #include <cmath>
15 #include <ctime>
16 #include <cstring>
17 #include <climits>
18 #include <cctype>
19 #include <cassert>
20 #include <functional>
21 #include <iterator>
22 #include <iomanip>
23 using namespace std;
24 //#pragma comment(linker,"/STACK:102400000,1024000")
25 
26 #define sti                set<int>
27 #define stpii            set<pair<int, int> >
28 #define mpii            map<int,int>
29 #define vi                vector<int>
30 #define pii                pair<int,int>
31 #define vpii            vector<pair<int,int> >
32 #define rep(i, a, n)     for (int i=a;i<n;++i)
33 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
34 #define clr                clear
35 #define pb                 push_back
36 #define mp                 make_pair
37 #define fir                first
38 #define sec                second
39 #define all(x)             (x).begin(),(x).end()
40 #define SZ(x)             ((int)(x).size())
41 #define lson            l, mid, rt<<1
42 #define rson            mid+1, r, rt<<1|1
43 
44 const int maxn = 2e5+5;
45 int Y[maxn], ny = 0;
46 int c[maxn];
47 
48 int main() {
49     ios::sync_with_stdio(false);
50     #ifndef ONLINE_JUDGE
51         freopen("data.in", "r", stdin);
52         freopen("data.out", "w", stdout);
53     #endif
54     
55     int n;
56     int x, y;
57     vpii vp;
58     
59     scanf("%d", &n);
60     rep(i, 0, n) {
61         scanf("%d%d", &x, &y);
62         vp.pb(mp(x, y));
63         Y[i] = y;
64     }
65     
66     sort(all(vp));
67     sort(Y, Y+n);
68     ny = unique(Y, Y+n) - Y;
69     
70     int i = 0, j;
71     __int64 ans = 0;
72     
73     while (i < n) {
74         j = i;
75         while (i<n && vp[i].fir==vp[j].fir) {
76             vp[i].sec = lower_bound(Y, Y+ny, vp[i].sec) - Y;
77             ans += c[vp[i].sec];
78             ++i;
79         }
80         ans += 1LL * (i-j) * (i-j-1) / 2;
81         while (j < i) {
82             ++c[vp[j].sec];
83             ++j;
84         } 
85     }
86     
87     printf("%I64d
", ans);
88     
89     #ifndef ONLINE_JUDGE
90         printf("time = %d.
", (int)clock());
91     #endif
92     
93     return 0;
94 }

2. Image Preview
2.1 题目描述
手机上有n张照片，翻看照片仅仅能翻看相邻的照片（1与n相邻），每次翻看花费a秒。
手机一直处于垂直方向，照片可能为水平或垂直方向，当照片与手机方向不同时，需要花费额外b秒旋转。
观看照片需要1秒，同时可以跳过已经看过的照片，没有看过的照片则必须观看。求在时间T内最多观看多少照片。

2.2 基本思路
假设在时间$T$内最多观看$m$张照片，并且移动到没看过的照片必须观看。显然，这$m$个照片必然形成一个连续的区间（假定1与n连续）。
$L[i], R[i]$分别表示从1（起始位置）逆时针和顺时针看过$i$张照片所用的时间。
因此，我们可以对$m$进行二分，判断$min {L[k] + R[m-1-k] - T_{skip} - L[1]} le T$。这里$T_{skip} = a * min (k, m-1-k)$。
$L[i], R[i]$可以在$O(n)$时间内预处理，因此时间复杂度为$O(nlogn)$。

2.3 代码

  1 /* B */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <bitset>
 12 #include <algorithm>
 13 #include <cstdio>
 14 #include <cmath>
 15 #include <ctime>
 16 #include <cstring>
 17 #include <climits>
 18 #include <cctype>
 19 #include <cassert>
 20 #include <functional>
 21 #include <iterator>
 22 #include <iomanip>
 23 using namespace std;
 24 //#pragma comment(linker,"/STACK:102400000,1024000")
 25 
 26 #define sti                set<int>
 27 #define stpii            set<pair<int, int> >
 28 #define mpii            map<int,int>
 29 #define vi                vector<int>
 30 #define pii                pair<int,int>
 31 #define vpii            vector<pair<int,int> >
 32 #define rep(i, a, n)     for (int i=a;i<n;++i)
 33 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 34 #define clr                clear
 35 #define pb                 push_back
 36 #define mp                 make_pair
 37 #define fir                first
 38 #define sec                second
 39 #define all(x)             (x).begin(),(x).end()
 40 #define SZ(x)             ((int)(x).size())
 41 #define lson            l, mid, rt<<1
 42 #define rson            mid+1, r, rt<<1|1
 43 
 44 const int maxn = 5e5+5;
 45 int n, a, b, T;
 46 char s[maxn];
 47 int L[maxn], R[maxn];
 48 
 49 bool judge(int m) {
 50     int mn = INT_MAX, tmp;
 51 
 52     --m;
 53     for (int ln=m,rn=0; ln>=0; --ln,++rn) {
 54         tmp = L[ln] + R[rn] -L[0] + min(ln, rn) * a;
 55         mn = min(tmp, mn);
 56     }
 57 
 58     return mn<=T;
 59 }
 60 
 61 void solve() {
 62     R[0] = s[0]=='w' ? b+1:1;
 63     rep(i, 1, n) {
 64         R[i] += R[i-1];
 65         R[i] += a + 1;
 66         if (s[i] == 'w')
 67             R[i] += b;
 68     }
 69     L[0] = s[0]=='w' ? b+1:1;
 70     rep(i, 1, n) {
 71         L[i] += L[i-1];
 72         L[i] += a + 1;
 73         if (s[n-i] == 'w')
 74             L[i] += b;
 75     }
 76     
 77     if (T < R[0]) {
 78         puts("0");
 79         return ;
 80     }
 81 
 82     int l = 1;
 83     int r = n;
 84     int mid;
 85     int ans = 0;
 86 
 87     while (l <= r) {
 88         mid = (l + r) >> 1;
 89         if (judge(mid)) {
 90             ans = mid;
 91             l = mid + 1;
 92         } else {
 93             r = mid - 1;
 94         }
 95     }
 96 
 97     printf("%d
", ans);
 98 }
 99 
100 int main() {
101     ios::sync_with_stdio(false);
102     #ifndef ONLINE_JUDGE
103         freopen("data.in", "r", stdin);
104         freopen("data.out", "w", stdout);
105     #endif
106 
107     scanf("%d%d%d%d", &n,&a,&b,&T);
108     scanf("%s", s);
109     solve();
110 
111     #ifndef ONLINE_JUDGE
112         printf("time = %d.
", (int)clock());
113     #endif
114 
115     return 0;
116 }

3. Table Compression
3.1 题目描述
将矩阵$A_{n imes m}$压缩成$B_{n imes m}, b_ij > 0$。
同时，$forall a_ij,a_ik$中的大小关系与$B$中对应元素保持一致，$forall a_ij,a_kj$同样保持一致。
找到这样一个$B$，并是$B$中的最大值最小。

3.2 基本思路
先考虑$A$中的元素均不相同，那么显然可以建立一个有向图（较小值指向较大值），然后进行拓扑。
然而$n cdot m le 10^6$，这也导致了这样朴素建图边会超多$10^9$左右。
那么，能不能减少一些没用的边呢？显然可以，考虑最普通的行矩阵$[1 2 3 4]$。
1指向2就可以了，其实并不需要1指向3，因为2更接近3，当2确定，3才可以确定。
因此，我们可以对$A$的每行每列都排序后，然后按照次序建边。这样，这个图的规模控制在了$O(nm)$。
不仅如此，那么如果存在相同元素，这样就增加了一定的复杂程度。
处理方法，就是将增加一个$eq$邻接表，存储处在同一行或同一列的元素，因为，这些元素的值同时确定。
这样，当进行拓扑时，我们直接从最小值拓扑开始即可（对原始数据排序）。
算法复杂度为$O(nmlog(nm))$。

3.3 代码

  1 /* C */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <bitset>
 12 #include <algorithm>
 13 #include <cstdio>
 14 #include <cmath>
 15 #include <ctime>
 16 #include <cstring>
 17 #include <climits>
 18 #include <cctype>
 19 #include <cassert>
 20 #include <functional>
 21 #include <iterator>
 22 #include <iomanip>
 23 using namespace std;
 24 //#pragma comment(linker,"/STACK:102400000,1024000")
 25 
 26 #define sti                set<int>
 27 #define stpii            set<pair<int, int> >
 28 #define mpii            map<int,int>
 29 #define vi                vector<int>
 30 #define pii                pair<int,int>
 31 #define vpii            vector<pair<int,int> >
 32 #define rep(i, a, n)     for (int i=a;i<n;++i)
 33 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 34 #define clr                clear
 35 #define pb                 push_back
 36 #define mp                 make_pair
 37 #define fir                first
 38 #define sec                second
 39 #define all(x)             (x).begin(),(x).end()
 40 #define SZ(x)             ((int)(x).size())
 41 #define lson            l, mid, rt<<1
 42 #define rson            mid+1, r, rt<<1|1
 43 
 44 const int maxn = 1e6+5;
 45 vector<vi> g;
 46 vi E[maxn];
 47 vi eq[maxn];
 48 bool visit[maxn];
 49 int Q[maxn];
 50 int val[maxn];
 51 int ans[maxn];
 52 int n, m;
 53 
 54 void solve() {
 55     rep(i, 0, n) {
 56         vpii vp;
 57         rep(j, 0, m)
 58             vp.pb(mp(g[i][j], j));
 59         sort(all(vp));
 60         
 61         rep(j, 1, m) {
 62             int uid = i*m + vp[j-1].sec;
 63             int vid = i*m + vp[j].sec;
 64             if (vp[j].fir == vp[j-1].fir) {
 65                 eq[uid].pb(vid);
 66                 eq[vid].pb(uid);
 67             } else {
 68                 E[vid].pb(uid);
 69             }
 70         }
 71     }
 72     
 73     rep(j, 0, m) {
 74         vpii vp;
 75         rep(i, 0, n)
 76             vp.pb(mp(g[i][j], i));
 77         sort(all(vp));
 78         
 79         rep(i, 1, n) {
 80             int uid = vp[i-1].sec*m + j;
 81             int vid = vp[i].sec*m + j;
 82             if (vp[i].fir == vp[i-1].fir) {
 83                 eq[uid].pb(vid);
 84                 eq[vid].pb(uid);
 85             } else {
 86                 E[vid].pb(uid);
 87             }
 88         }
 89     }
 90     
 91     int tot = n * m;
 92     int u, v;
 93     vpii vp;
 94     
 95     rep(i, 0, tot)
 96         vp.pb(mp(val[i], i));
 97         
 98     sort(all(vp));
 99     
100     rep(i, 0, tot) {
101         int id = vp[i].sec;
102         if (visit[id])
103             continue;
104         int l = 0, r = 0;
105         
106         Q[r++] = id;
107         visit[id] = true;
108         while (l < r) {
109             u = Q[l++];
110             int sz = SZ(eq[u]);
111             rep(j, 0, sz) {
112                 v = eq[u][j];
113                 if (!visit[v]) {
114                     visit[v] = true;
115                     Q[r++] = v;
116                 }
117             }
118         }
119         
120         int mx = 0;
121         rep(j, 0, r) {
122             u = Q[j];
123             int sz = SZ(E[u]);
124             rep(k, 0, sz) {
125                 v = E[u][k];
126                 mx = max(mx, ans[v]);
127             }
128         }
129         
130         ++mx;
131         rep(j, 0, r)
132             ans[Q[j]] = mx;
133     }
134     
135     int cnt = 0;
136     rep(i, 0, n) {
137         rep(j, 0, m) {
138             if (j)
139                 putchar(' ');
140             printf("%d", ans[cnt++]);
141         }
142         putchar('
');
143     }
144 }
145 
146 int main() {
147     ios::sync_with_stdio(false);
148     #ifndef ONLINE_JUDGE
149         freopen("data.in", "r", stdin);
150         freopen("data.out", "w", stdout);
151     #endif
152     
153     int x, cnt = 0;
154     
155     scanf("%d%d", &n, &m);
156     rep(i, 0, n) {
157         vi vc;
158         rep(j, 0, m) {
159             scanf("%d", &x);
160             val[cnt++] = x;
161             vc.pb(x);
162         }
163         g.pb(vc);
164     }
165     
166     solve();
167     
168     #ifndef ONLINE_JUDGE
169         printf("time = %d.
", (int)clock());
170     #endif
171     
172     return 0;
173 }

4. Zip-line
4.1 题目描述
$n$棵树，高度分别为$H_i, i in [1,n]$，m次查询。查询将$H_a$修改为$b$后，最长上升子序列的长度为多少？

4.2 基本思路
这题目就是求$LIS$。思路其实还是挺简单的，初始数组可以求得原始的$LIS$。
因此，修改后的长度至少为$|LIS|-1$，可能达到$|LIS|+1$或者$|LIS|$。
当修改的点不是关键点是，则长度至少为$|LIS|$，否则至少为$|LIS|-1$。
采用离线做，对所有m个查询按照$a$排序，然后使用树状数组或线段树可以计算$LIS$的长度。
$L[i]$表示从1开始以$i$为结尾的上升序列的长度，$R[i]$表示从$n$开始以$i$结尾的下降序列的长度（其实就是从$i$开始以$n$结尾的上升序列）。
$L[i]+R[i]-1$就是经过$i$的上升序列的长度，通过$L[i]+R[i]-1 == |LIS|$以及$cnt$数组的使用可以判定$i$是否为关键点。
$LL[i]$与$RR[i]$的定义了类似，但是针对的是$m$个查询的。因此，$LL[i]+RR[i]-1$就是经过查询修改的点的最长上升子序列的长度，计算过程与上述类似。
二者的最大值，就是修改后整个串的最长上升子序列的长度。
其实这题不难，排序后，就可以均摊了，复杂度为$O(nlgn)$。

4.3 代码

  1 /* D */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <bitset>
 12 #include <algorithm>
 13 #include <cstdio>
 14 #include <cmath>
 15 #include <ctime>
 16 #include <cstring>
 17 #include <climits>
 18 #include <cctype>
 19 #include <cassert>
 20 #include <functional>
 21 #include <iterator>
 22 #include <iomanip>
 23 using namespace std;
 24 //#pragma comment(linker,"/STACK:102400000,1024000")
 25 
 26 #define sti                set<int>
 27 #define stpii            set<pair<int, int> >
 28 #define mpii            map<int,int>
 29 #define vi                vector<int>
 30 #define pii                pair<int,int>
 31 #define vpii            vector<pair<int,int> >
 32 #define rep(i, a, n)     for (int i=a;i<n;++i)
 33 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 34 #define clr                clear
 35 #define pb                 push_back
 36 #define mp                 make_pair
 37 #define fir                first
 38 #define sec                second
 39 #define all(x)             (x).begin(),(x).end()
 40 #define SZ(x)             ((int)(x).size())
 41 #define lson            l, mid, rt<<1
 42 #define rson            mid+1, r, rt<<1|1
 43 
 44 typedef struct node_t {
 45     int a, b, id;
 46     
 47     friend bool operator< (const node_t& a, const node_t& b) {
 48         return a.a < b.a;
 49     }
 50 } node_t;
 51 
 52 const int maxn = 8e5+5;
 53 const int maxm = 4e5+5;
 54 int H[maxm], a[maxn], an = 1;
 55 int c[maxn];
 56 int ans[maxm];
 57 node_t Q[maxm];
 58 int L[maxm], R[maxm];
 59 int LL[maxm], RR[maxm];
 60 bool visit[maxn];
 61 int cnt[maxn];
 62 int n, m;
 63 
 64 inline int lowest(int x) {
 65     return -x & x;
 66 }
 67 
 68 int main() {
 69     ios::sync_with_stdio(false);
 70     #ifndef ONLINE_JUDGE
 71         freopen("data.in", "r", stdin);
 72         freopen("data.out", "w", stdout);
 73     #endif
 74     
 75     scanf("%d%d", &n, &m);
 76     rep(i, 1, n+1) {
 77         scanf("%d", &H[i]);
 78         a[an++] = H[i];
 79     }
 80     rep(i, 1, m+1) {
 81         scanf("%d%d", &Q[i].a, &Q[i].b);
 82         a[an++] = Q[i].b;
 83         Q[i].id = i;
 84     }
 85     sort(a+1, a+an);
 86     an = unique(a+1, a+an) - (a+1);
 87     rep(i, 1, n+1)    H[i] = lower_bound(a+1, a+an+1, H[i]) - a;
 88     rep(i, 1, m+1)    Q[i].b = lower_bound(a+1, a+an+1, Q[i].b) - a;
 89     
 90     memset(c, 0, sizeof(c));
 91     rep(i, 1, n+1) {
 92         int mx = 0;
 93         for (int j=H[i]-1; j; j-=lowest(j))
 94             mx = max(mx, c[j]);
 95         L[i] = ++mx;
 96         for (int j=H[i]; j<=an; j+=lowest(j))
 97             c[j] = max(c[j], mx);
 98     }
 99     
100     memset(c, 0, sizeof(c));
101     per(i, 1, n+1) {
102         int mx = 0;
103         for (int j=H[i]+1; j<=an; j+=lowest(j))
104             mx = max(mx, c[j]);
105         R[i] = ++mx;
106         for (int j=H[i]; j; j-=lowest(j))
107             c[j] = max(c[j], mx);
108     }
109     
110     int lis = 0;
111     rep(i, 1, n+1)
112         lis = max(lis, R[i]+L[i]-1);
113     
114     memset(visit, false, sizeof(visit));
115     memset(cnt, 0, sizeof(cnt));
116     rep(i, 1, n+1) {
117         if (L[i]+R[i]-1 == lis) {
118             visit[i] = true;
119             ++cnt[L[i]];
120         }
121     }
122     
123     rep(i, 1, n+1) {
124         if (visit[i] && cnt[L[i]]>1)
125             visit[i] = false;
126     }
127     
128     rep(i, 1, m+1) {
129         if (visit[Q[i].a])
130             ans[Q[i].id] = lis - 1;
131         else
132             ans[Q[i].id] = lis;
133     }
134     
135     sort(Q+1, Q+1+m);
136     
137     memset(c, 0, sizeof(c));
138     int j = 1;
139     rep(i, 1, m+1) {
140         while (j<Q[i].a && j<=n) {
141             int tmp = L[j];
142             for (int k=H[j]; k<=an; k+=lowest(k))
143                 c[k] = max(c[k], tmp);
144             ++j;
145         }
146         
147         int mx = 0;
148         for (int k=Q[i].b-1; k; k-=lowest(k))
149             mx = max(mx, c[k]);
150         LL[Q[i].id] = ++mx;
151     }
152     
153     memset(c, 0, sizeof(c));
154     j = n;
155     per(i, 1, m+1) {
156         while (j>Q[i].a && j) {
157             int tmp = R[j];
158             for (int k=H[j]; k; k-=lowest(k))
159                 c[k] = max(c[k], tmp);
160             --j;
161         }
162         
163         int mx = 0;
164         for (int k=Q[i].b+1; k<=an; k+=lowest(k))
165             mx = max(mx, c[k]);
166         RR[Q[i].id] = ++mx;
167     }
168     
169     rep(i, 1, m+1) {
170         ans[i] = max(ans[i], LL[i]+RR[i]-1);
171         printf("%d
", ans[i]);
172     }
173     
174     #ifndef ONLINE_JUDGE
175         printf("time = %d.
", (int)clock());
176     #endif
177     
178     return 0;
179 }