莫队/分块题目泛做

题目1 BZOJ2453 / 2120

算法讨论：

用pre[i]表示与第i个位置颜色相同的上个位置在哪里，那么对于l...r内，如果一个位置的pre[i] < l，则说明这个颜色是第一次出现。

然后暴力分块。因为修改的次数很少，所以每次修改就重新计算pre[i],对于涉及的块重新构块。然后对于整块的查询，直接在排好序的pre上二分就可以了。

  1 #include <bits/stdc++.h>
  2  
  3 using namespace std;
  4  
  5 const int M = 1000000 + 5;
  6 const int N = 10000 + 5;
  7 const int K = 110;
  8  
  9 inline int read() {
 10   int x = 0;
 11   char c = getchar();
 12  
 13   while(!isdigit(c)) c = getchar();
 14   while(isdigit(c)) {
 15     x = x * 10 + c - '0';
 16     c = getchar();
 17   }
 18   return x;
 19 }
 20  
 21 char ss[5];
 22 int n, m, size, tk;
 23 int ckn[N], b[N], pre[N], last[M], a[N];
 24 int l[K], r[K];
 25  
 26 void prepare() {
 27   size = (int) sqrt(n);
 28   for(int i = 1; i <= n; ++ i) ckn[i] = (i - 1) / size + 1;
 29   tk = n / size + 1 - (n % size == 0);
 30   for(int i = 1; i <= tk; ++ i) {
 31     l[i] = (i - 1) * size + 1;
 32     r[i] = min(i * size, n);
 33     for(int j = l[i]; j <= r[i]; ++ j) {
 34       b[j] = pre[j];
 35     }
 36     sort(b + l[i], b + r[i] + 1);
 37   }
 38 }
 39  
 40 void reset(int num) {
 41   for(int i = l[num]; i <= r[num]; ++ i) {
 42     b[i] = pre[i];
 43   }
 44   sort(b + l[num], b + r[num] + 1);
 45 }
 46  
 47 void update(int x, int v) {
 48   int tp;
 49    
 50   for(int i = 1; i <= n; ++ i) last[a[i]] = 0;
 51   a[x] = v;
 52   for(int i = 1; i <= n; ++ i) {
 53     tp = pre[i];
 54     pre[i] = last[a[i]];
 55     if(tp != pre[i]) reset(ckn[i]);
 56     last[a[i]] = i;
 57   }
 58 }
 59  
 60 int bs(int L, int R, int V) {
 61   int mid, res, Down = L;
 62  
 63   if(b[R] < V) return R - L + 1;
 64   if(b[L] >= V) return 0;
 65   while(L <= R) {
 66     mid = L + (R - L) / 2;
 67     if(b[mid] < V) {
 68       L = mid + 1;
 69       res = mid;
 70     }
 71     else
 72       R = mid - 1;
 73   }
 74   return res - Down + 1;
 75 }
 76  
 77 void query(int L, int R) {
 78   int n1 = ckn[L], n2 = ckn[R];
 79   int res = 0;
 80    
 81   if(n1 == n2) {
 82     for(int i = L; i <= R; ++ i) {
 83       if(pre[i] < L) ++ res;
 84     }
 85     printf("%d
", res);
 86   }
 87   else {
 88     for(int i = L; i <= r[n1]; ++ i)
 89       if(pre[i] < L) ++ res;
 90     for(int i = l[n2]; i <= R; ++ i)
 91       if(pre[i] < L) ++ res;
 92     for(int i = n1 + 1; i < n2; ++ i)
 93       res += bs(l[i], r[i], L);
 94     printf("%d
", res);
 95   }
 96 }
 97  
 98 int main() {
 99   int x, y;
100    
101   n = read(); m = read();
102   for(int i = 1; i <= n; ++ i) a[i] = read();
103   for(int i = 1; i <= n; ++ i) {
104     pre[i] = last[a[i]];
105     last[a[i]] = i;
106   }
107   prepare();
108   for(int i = 1; i <= m; ++ i) {
109     scanf("%s", ss);
110     x = read(); y = read();
111     if(ss[0] == 'Q') {
112       query(x, y);
113     }
114     else {
115       update(x, y);
116     }
117   }
118   return 0;
119 }

BZOJ2120

题目2 BZOJ3052 WC2013 糖果公园

算法讨论：

带修改的树上莫队。

  1 #include <iostream>
  2 #include <cstdlib>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <algorithm>
  6 #include <cctype>
  7 #include <cmath>
  8 #include <stack>
  9 
 10 using namespace std;
 11 
 12 const int N = 100000 + 5;
 13 typedef long long ll;
 14 
 15 inline int read() {
 16   int x = 0;
 17   char c = getchar();
 18 
 19   while(!isdigit(c)) c = getchar();
 20   while(isdigit(c)) {
 21     x = x * 10 + c - '0';
 22     c = getchar();
 23   }
 24   return x;
 25 }
 26 
 27 int buf[30];
 28 
 29 inline void output(ll x) {
 30   int p = 0;
 31 
 32   buf[0] = 0;
 33   if(x == 0) p ++;
 34   else {
 35     while(x) {
 36       buf[p ++] = x % 10;
 37       x /= 10;
 38     }
 39   }
 40   for(int j = p - 1; j >= 0; -- j)
 41     putchar('0' + buf[j]);
 42 }
 43 
 44 ll ans[N], tot = 0;
 45 int n, m, q, size, cnt, tk, tim;
 46 int head[N], fa[N], f[N][18], seq[N], v[N], w[N];
 47 int ckn[N], depth[N], son[N], pre[N], c[N];
 48 bool flag[N]; int vis[N];
 49 stack <int> s;
 50 
 51 struct Edge {
 52   int from, to, next;
 53 }edges[N << 1];
 54 struct Query {
 55   int x, v, pre;
 56 }C[N];
 57 struct query {
 58   int id, u, v, t;
 59   bool operator < (const query &k) const {
 60     if(ckn[u] == ckn[k.u] && ckn[v] == ckn[k.v]) return t < k.t;
 61     else if(ckn[u] == ckn[k.u]) return ckn[v] < ckn[k.v];
 62     else return ckn[u] < ckn[k.u];
 63   }
 64 }Q[N];
 65 
 66 void insert(int from, int to) {
 67   ++ cnt;
 68   edges[cnt].from = from; edges[cnt].to = to;
 69   edges[cnt].next = head[from]; head[from] = cnt;
 70 }
 71 
 72 void dfs(int u, int f) {
 73   fa[u] = f; seq[u] = ++ tim;
 74   for(int i = head[u]; i; i = edges[i].next) {
 75     int v = edges[i].to;
 76 
 77     if(v != f) {
 78       depth[v] = depth[u] + 1;
 79       dfs(v, u);
 80       son[u] += son[v];
 81       if(son[u] >= size) {
 82         ++ tk;
 83         son[u] = 0;
 84         while(!s.empty()) {
 85           int cur = s.top(); s.pop();
 86           ckn[cur] = tk;
 87         }
 88       }
 89     }
 90   }
 91   s.push(u); son[u] ++;
 92 }
 93 
 94 void prepare() {
 95   memset(f, -1, sizeof f);
 96   for(int i = 1; i <= n; ++ i) f[i][0] = fa[i];
 97   for(int j = 1; (1 << j) <= n; ++ j) {
 98     for(int i = 1; i <= n; ++ i) {
 99       if(f[i][j - 1] != -1) {
100         f[i][j] = f[f[i][j - 1]][j - 1];
101       }
102     }
103   }
104 }
105 
106 int lca(int a, int b) {
107   int i;
108 
109   if(depth[a] < depth[b]) swap(a, b);
110   for(i = 0; (1 << i) <= depth[a]; ++ i);
111   -- i;
112   for(int j = i; j >= 0; -- j) {
113     if(depth[a] - depth[b] >= (1 << j))
114       a = f[a][j];
115   }
116   if(a == b) return a;
117   for(int j = i; j >= 0; -- j) {
118     if(f[a][j] != -1 && f[a][j] != f[b][j]) {
119       a = f[a][j];
120       b = f[b][j];
121     }
122   }
123   return f[a][0];
124 }
125 
126 void rever(int u) {
127   if(flag[u]) {
128     flag[u] = false;
129     tot -= 1LL * w[vis[c[u]]] * v[c[u]];
130     vis[c[u]] --;
131   }
132   else {
133     flag[u] = true;
134     vis[c[u]] ++;
135     tot += 1LL * w[vis[c[u]]] * v[c[u]];
136   }
137 }
138 
139 void Getpath(int u, int fi) {
140   while(u != fi) {
141     rever(u);
142     u = fa[u];
143   }
144 }
145 
146 void change(int x, int v) {
147   if(flag[x]) {
148     rever(x); c[x] = v; rever(x);
149   }
150   else c[x] = v;
151 }
152 
153 void solve(int nl, int nr, int &zl, int &zr, int ts) {
154   int Lca;
155 
156   Lca = lca(nl, zl);
157   Getpath(nl, Lca); Getpath(zl, Lca);
158   Lca = lca(nr, zr);
159   Getpath(nr, Lca); Getpath(zr, Lca);
160   Lca = lca(nl, nr);
161   rever(Lca); ans[Q[ts].id] = tot; rever(Lca);
162   zl = nl; zr = nr;
163 }
164 
165 #define ONLINE_JUDGE
166 
167 int main() {
168   //int __size__ =  64 <<20;  //这里谁<<20位，就是多少M的栈
169   //char*__p__ =(char*)malloc(__size__)+ __size__;
170   //__asm__("movl %0, %%esp
"::"r"(__p__));
171 
172 #ifndef ONLINE_JUDGE
173   freopen("park.in", "r", stdin);
174   freopen("park.out", "w", stdout);
175 #endif
176 
177   int x, y;
178 
179   n = read(); m = read(); q = read();
180   for(int i = 1; i <= m; ++ i) v[i] = read();
181   for(int i = 1; i <= n; ++ i) w[i] = read();
182   for(int i = 1; i < n; ++ i) {
183     x = read(); y = read();
184     insert(x, y); insert(y, x);
185   }
186   for(int i = 1; i <= n; ++ i) pre[i] = c[i] = read();
187   depth[1] = 1; //size = (int) pow((double) n, (double) 2 / 3);
188   size = 1500;
189   dfs(1, -1);
190   if(!s.empty()) {
191     ++ tk;
192     while(!s.empty()) {
193       int cur = s.top(); s.pop();
194       ckn[cur] = tk;
195     }
196   }
197   prepare();
198 
199   int type, t1 = 0, t2 = 0;
200   
201   for(int i = 1; i <= q; ++ i) {
202     type = read();
203     if(!type) {
204       ++ t1;
205       C[t1].x = read(); C[t1].v = read(); C[t1].pre = pre[C[t1].x];
206       pre[C[t1].x] = C[t1].v;
207     }
208     else {
209       ++ t2;
210       Q[t2].u = read(); Q[t2].v = read(); Q[t2].id = t2; Q[t2].t = t1;
211       if(seq[Q[t2].u] > seq[Q[t2].v]) swap(Q[t2].u, Q[t2].v);
212     }
213   }
214 
215   int L = 1, R = 1;
216 
217   sort(Q + 1, Q + t2 + 1);
218   for(int i = 1; i <= Q[1].t; ++ i) {
219     change(C[i].x, C[i].v);
220   }
221   solve(Q[1].u, Q[1].v, L, R, 1);
222   for(int i = 2; i <= t2; ++ i) {
223     for(int t = Q[i - 1].t + 1; t <= Q[i].t; ++ t)
224       change(C[t].x, C[t].v);
225     for(int t = Q[i - 1].t; t > Q[i].t; -- t)
226       change(C[t].x, C[t].pre);
227     solve(Q[i].u, Q[i].v, L, R, i);
228   }
229   for(int i = 1; i <= t2; ++ i) {
230     output(ans[i]);
231     puts("");
232   }
233   
234 #ifndef ONLINE_JUDGE
235   fclose(stdin); fclose(stdout);
236 #endif
237   return 0;
238 }

BZOJ 3052

题目3 NOI2003 文本编辑器

算法讨论：

块状链表。支持插入、删除、找到第x个数的位置等操作。

对于插入操作，

如果要插入的当前块的大小已经满块
那么就新建立一个块，插到原来的两块之间，修改块之间的指针
然后把这个新块之前的块的光标之后的东西复制到新块，然后更新原块的size
然后比较这两个块的大小，把字符插入到较小的那个块中去。

对于删除操作

首先判断当前块的光标之后的元素个数是否比删除的东西多，如果多的话，就直接在块内删除
如果不是，则直接把块改了。

  1 #include <cstdlib>
  2 #include <iostream>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <cstdio>
  6  
  7 using namespace std;
  8  
  9 const int K = 3000 + 5;
 10  
 11 char opt[10];
 12 int m;
 13 int cur_mouse, cur_blo, tk, size;
 14 //cur_mouse 记录光标在某个块内的位置
 15 //cur_blo记录当前在某个块 tk是块的总数  size是块的上限大小
 16 struct Node {
 17   char s[K];
 18   int sz, pre, next;
 19 }blo[K];
 20  
 21 void Move() {
 22   int mouse;
 23   scanf("%d", &mouse);
 24   cur_blo = blo[0].next;
 25   while(mouse > blo[cur_blo].sz) {
 26     mouse -= blo[cur_blo].sz; cur_blo = blo[cur_blo].next;
 27   }
 28   cur_mouse = mouse;
 29 }
 30  
 31 void Insert() {
 32   int cmd, imouse = cur_mouse, iblo = cur_blo;
 33   char c;
 34   scanf("%d", &cmd);
 35   c = getchar();
 36   while(cmd --) {
 37     while(c < 32 || c > 126) c = getchar();
 38     if(blo[iblo].sz == size) {
 39       ++ tk;
 40       blo[tk].next = blo[iblo].next;
 41       blo[tk].pre = iblo; blo[tk].sz = size - imouse;
 42       blo[blo[iblo].next].pre = tk;
 43       blo[iblo].next = tk;
 44       for(int i = 1; i <= blo[tk].sz; ++ i)
 45         blo[tk].s[i] = blo[iblo].s[imouse + i];
 46       blo[iblo].sz = imouse;
 47       if(blo[tk].sz < blo[iblo].sz) {
 48         imouse = 0; iblo = tk;
 49       }
 50     }
 51     blo[iblo].sz ++;
 52     for(int i = blo[iblo].sz; i > imouse; -- i) {
 53       blo[iblo].s[i] = blo[iblo].s[i - 1];
 54     }
 55     blo[iblo].s[++ imouse] = c;
 56     c = getchar();
 57   }
 58 }
 59  
 60 void Delete() {
 61   int cmd, imouse = cur_mouse, iblo = cur_blo;
 62   scanf("%d", &cmd);
 63   while(cmd) {
 64     int left = blo[iblo].sz - imouse;
 65     if(cmd > left) {
 66       cmd -= left; blo[iblo].sz = imouse;
 67       iblo = blo[iblo].next;
 68       imouse = 0;
 69     }
 70     else {
 71       for(int i = imouse + cmd + 1; i <= blo[iblo].sz; ++ i)
 72         blo[iblo].s[i - cmd] = blo[iblo].s[i];
 73       blo[iblo].sz -= cmd;
 74       cmd = 0;
 75     }
 76   }
 77 }
 78  
 79 void Next() {
 80   if(cur_mouse != blo[cur_blo].sz) cur_mouse ++;
 81   else {
 82     cur_blo = blo[cur_blo].next;
 83     while(blo[cur_blo].sz == 0) {
 84       blo[blo[cur_blo].pre].next = blo[cur_blo].next;
 85       blo[blo[cur_blo].next].pre = blo[cur_blo].pre;
 86       cur_blo = blo[cur_blo].next;
 87     }
 88     cur_mouse = 1;
 89   }
 90 }
 91  
 92 void Prev() {
 93   if(cur_mouse) cur_mouse --;
 94   else {
 95     cur_blo = blo[cur_blo].pre;
 96     while(blo[cur_blo].sz == 0) {
 97       blo[blo[cur_blo].pre].next = blo[cur_blo].next;
 98       blo[blo[cur_blo].next].pre = blo[cur_blo].pre;
 99       cur_blo = blo[cur_blo].pre;
100     }
101     cur_mouse = blo[cur_blo].sz - 1;
102   }
103 }
104  
105 void Get() {
106   int cmd, imouse = cur_mouse, iblo = cur_blo;
107   scanf("%d", &cmd);
108   while(cmd) {
109     if(blo[iblo].sz == 0) {
110       blo[blo[iblo].next].pre = blo[iblo].pre;
111       blo[blo[iblo].pre].next = blo[iblo].next;
112       iblo = blo[iblo].next;
113     }
114     int left = blo[iblo].sz - imouse;
115     if(cmd > left) {
116       for(int i = imouse + 1; i <= blo[iblo].sz; ++ i)
117         putchar(blo[iblo].s[i]);
118       cmd -= left;
119       imouse = 0;
120       iblo = blo[iblo].next;
121     }
122     else {
123       for(int i = imouse + 1; i <= imouse + cmd; ++ i)
124         putchar(blo[iblo].s[i]);
125       cmd = 0;
126     }
127   }
128   puts("");
129 }
130  
131 #define ONLINE_JUDGE
132  
133 int main() {
134 #ifndef ONLINE_JUDGE
135   freopen("editor2003.in", "r", stdin);
136   freopen("editor2003.out", "w", stdout);
137 #endif
138  
139   scanf("%d", &m);
140   size = 2000;
141   tk = 1; cur_blo = 1;
142   blo[0].next = 1;//忘记链表初始化。。额。
143   while(m --) {
144     scanf("%s", opt);
145     if(opt[0] == 'M') Move();
146     else if(opt[0] == 'I') Insert();
147     else if(opt[0] == 'D') Delete();
148     else if(opt[0] == 'G') Get();
149     else if(opt[0] == 'P') Prev();
150     else if(opt[0] == 'N') Next();
151   }
152  
153 #ifndef ONLINE_JUDGE
154   fclose(stdin); fclose(stdout);
155 #endif
156  
157   return 0;
158 }

NOI 2003

莫队/分块 题目泛做

莫队/分块题目泛做