[关闭]
@ljt12138 2017-04-03T19:29:17.000000Z 字数 12543 阅读 924

bzoj刷题记录 4.2-4.4

月考完了。凭借多年应试经验连蒙带猜应付掉，然而坠稳的数学跪烂[没考过班里要学文的dalao]...还是认真刷OJ吧。

bzoj1211：[HNOI2004]树的计数

从Zars19的blog里学习了一个prufer编码。经典文章是matrix67 dalao的介绍，传送门。
总之就是把无根有标号树和长度为n−2的数组建立了双射，然后树上计数就变成序列计数了。总方案是：

(n−2d1−1)(n−2−(d1−1)d2−1)(n−2−(d1−1)−(d2−1)d3−1))…

然而直接组合数莫名其妙的跪，于是阶乘展开变成：

(n−2)!∏i(di−1)!

看到阶乘然后就可以上下分解质因数随便减一减就好。另外特判坑死人。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int prime[155], tot = 0;
  5. int n, s, cnt = 0;
  6. int c[155];
  8. void get_prime()
  9. {
  10.     for (int i = 2; i <= n; i++) {
  11.         int flg = 0;
  12.         for (int j = 2; j < i; j++)
  13.             if (i%j == 0) {
  14.                 flg = 1;
  15.                 break;
  16.             }
  17.         if (!flg) {
  18.             prime[++tot] = i;
  19.             for (int j = i; (n-2)/j > 0; j *= i)
  20.                 c[tot] += (n-2)/j;
  21.         }
  22.     }
  23. }
  25. void div(int nd)
  26. {
  27.     for (int i = 1; i <= tot; i++) {
  28.         for (int j = prime[i]; j <= nd; j *= prime[i])
  29.             c[i] -= nd/j;
  30.     }
  31. }
  33. long long power(int a, int n)
  34. {
  35.     if (n == 0) return 1;
  36.     long long p = power(a, n>>1);
  37.     p *= p, p *= (n&1)?a:1;
  38.     return p;
  39. }
  41. int main()
  42. {
  43.     scanf("%d", &n);
  44.     get_prime();
  45.     long long ans = 1;
  46.     if (n == 1) {
  47.         int d; scanf("%d", &d);
  48.         cout << (d == 0) << endl;
  49.         return 0;
  50.     }
  51.     for (int i = 1; i <= n; i++) {
  52.         int d; scanf("%d", &d);
  53.         if (d == 0) {
  54.             cout << 0 << endl;
  55.             return 0;
  56.         }
  57.         div(d-1);
  58.         cnt += d-1;
  59.     }
  60.     if (cnt != n-2) cout << 0 << endl;
  61.     else {
  62.         for (int i = 1; i <= tot; i++) {
  63.             ans *= power(prime[i], c[i]);
  64.         }
  65.         cout << ans << endl;
  66.     }
  67.     return 0;
  68. }

bzoj1030：文本生成器

AC自动机上dp处理不包含任何一个串的方案总数，然后减去就好。
顺便熟练一波AC自动机。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. struct ACM {
  5.     struct node {
  6.         bool finish;
  7.         int chl[26], fail;
  8.         node():finish(0),fail(0)
  9.         { memset(chl, 0, sizeof chl); }
  10.     } tree[20005];
  11.     int root, top;
  12.     queue<int> que;
  13.     ACM():root(0),top(0){}
  14.     void push(int &nd, const char *str)
  15.     {
  16.         if (nd == 0) nd = ++top;
  17.         if (*str == '\0') tree[nd].finish = 1;
  18.         else push(tree[nd].chl[*str-'A'], str+1);
  19.     }
  20.     void push(const char *str) {push(root, str); }
  21.     void init()
  22.     {
  23.         que.push(root); tree[root].fail = 0;
  24.         while (!que.empty()) {
  25.             int tp = que.front(); que.pop();
  26.             tree[tp].finish |= tree[tree[tp].fail].finish;
  27.             for (int i = 0; i < 26; i++) {
  28.                 if (!tree[tp].chl[i]) continue;
  29.                 int nd = tree[tp].fail;
  30.                 while (nd && !tree[nd].chl[i]) nd = tree[nd].fail;
  31.                 tree[tree[tp].chl[i]].fail = nd?tree[nd].chl[i]:root;
  32.                 tree[tree[tp].chl[i]].finish |= tree[tp].finish;
  33.                 que.push(tree[tp].chl[i]);
  34.             }
  35.         }
  36.     }
  37.     void dfs(int nd, int tab = 0)
  38.     {
  39.         if (!nd) return;
  40.         for (int i = 1; i <= tab; i++) putchar(' ');
  41.         printf("%d(%d, %d) : ", nd, tree[nd].fail, tree[nd].finish);
  42.         for (int i = 0; i < 26; i++)
  43.             if (tree[nd].chl[i]) printf("--%c--> %d; ", i+'A', tree[nd].chl[i]);
  44.         puts("");
  45.         for (int i = 0; i < 26; i++)
  46.             if (tree[nd].chl[i]) dfs(tree[nd].chl[i], tab+2);
  47.     }
  48. } ACM;
  50. int dp[105][20005];
  52. int dfs(int m, int nd)
  53. {
  54.     if (ACM.tree[nd].finish) return 0;
  55.     if (m == 0) return 1;
  56.     if (dp[m][nd] != -1) return dp[m][nd];
  57.     dp[m][nd] = 0;
  58.     for (int i = 0; i < 26; i++) {
  59.         int p = nd;
  60.         while (p && !ACM.tree[p].chl[i]) p = ACM.tree[p].fail;
  61.         if (p) (dp[m][nd] += dfs(m-1, ACM.tree[p].chl[i])) %= 10007;
  62.         else (dp[m][nd] += dfs(m-1, ACM.root)) %= 10007;
  63.     }
  64.     return dp[m][nd];
  65. }
  67. int power(int a, int n)
  68. {
  69.     if (n == 0) return 1;
  70.     int p = power(a, n>>1);
  71.     (p *= p) %= 10007;
  72.     if (n&1) (p *= a) %= 10007;
  73.     return p;
  74. }
  76. char str[105];
  77. int n, m;
  79. int main()
  80. {
  81.     memset(dp, -1, sizeof dp);
  82.     scanf("%d%d", &n, &m);
  83.     for (int i = 1; i <= n; i++) {
  84.         scanf("%s", str);
  85.         ACM.push(str);
  86.     }
  87.     ACM.init();
  88.     int ans = power(26, m)-dfs(m, ACM.root);
  89.     ((ans %= 10007) += 10007) %= 10007;
  90.     cout << ans << endl;
  91.     return 0;
  92. }

bzoj1016：[JSOI2008]最小生成树计数

原来讲过的题然而一直没有做。
按边长从小到大排，每次做一个Matrix_Tree生成森林计数，然后把能缩的缩在一起。除了特判1A。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 105, MAXM = 1005;
  5. struct node {
  6.     int i, j, d;
  7.     friend bool operator < (const node &a, const node &b)
  8.     { return a.d < b.d; }
  9. } edge[MAXM];
  10. int n, m;
  11. int gp[MAXN], vis[MAXN], gt; // 缩在一起的点的新编号
  12. double g[MAXN][MAXN]; // 求解行列式
  14. struct ufs {
  15.     int fa[MAXN];
  16.     void clear()
  17.     { memset(fa, 0, sizeof fa); }
  18.     ufs(){clear(); }
  19.     inline int findf(int nd)
  20.     { return fa[nd]?fa[nd] = findf(fa[nd]):nd; }
  21.     void link(int i, int j)
  22.     {
  23.         int p = findf(i), q = findf(j);
  24.         if (p != q) fa[p] = q;
  25.     }
  26. } UFS, u2;
  28. int calc()
  29. {
  30.     if (gt == 0) return 1;
  31.     gt--;
  32.     double ans = 1;
  33.     for (int i = 1; i <= gt; i++) {
  34.         if (g[i][i] == 0) {
  35.             int k = i+1; while (!g[k][i]) k++;
  36.             swap(g[i], g[k]);
  37.         }
  38.         ans *= g[i][i];
  39.         for (int j = i+1; j <= gt; j++) {
  40.             double t = -g[j][i]/g[i][i];
  41.             for (int k = i; k <= gt; k++)
  42.                 g[j][k] += g[i][k]*t;
  43.         }
  44.     }
  45.     // cout << ans << endl;
  46.     return int(ans+0.05)%31011;
  47. }
  49. int main()
  50. {
  51.     scanf("%d%d", &n, &m);
  52.     for (int i = 1; i <= m; i++)
  53.         scanf("%d%d%d", &edge[i].i, &edge[i].j, &edge[i].d);
  54.     sort(edge+1, edge+m+1);
  55.     long long ans = 1;
  56.     for (int i = 1; i <= m; ) {
  57.         // cout << "--" << i <<" " << edge[i].d<< endl;
  58.         int d = edge[i].d;
  59.         memset(vis, 0, sizeof vis);
  60.         memset(g, 0, sizeof g);
  61.         u2.clear();
  62.         gt = 0;
  63.         for (int j = i; j <= m && edge[j].d == d; j++) {
  64.             int p = UFS.findf(edge[j].i), q = UFS.findf(edge[j].j);
  65.             if (p==q) continue;
  66.             if (!vis[p]) gp[p] = ++gt, vis[p] = 1;
  67.             if (!vis[q]) gp[q] = ++gt, vis[q] = 1;
  68.             g[gp[p]][gp[q]]--, g[gp[q]][gp[p]]--, g[gp[p]][gp[p]]++, g[gp[q]][gp[q]]++, u2.link(gp[p], gp[q]);
  69.         } // 建图
  70.         if (gt == 1) break;
  71.         for (int k = 1; k <= gt; k++)
  72.             for (int j = k+1; j <= gt; j++) {
  73.                 // cout << k << " " << j << endl;
  74.                 if (u2.findf(k) != u2.findf(j))
  75.                     u2.link(k, j), g[k][j] = g[j][k] = -1, g[k][k]++, g[j][j]++;
  76.             }
  77.         // 建桥
  78.         (ans *= calc()) %= 31011; // matrix_tree theory
  79.         while (edge[i].d == d) UFS.link(edge[i].i, edge[i].j), i++; // 合并
  80.     }
  81.     for (int i = 1; i <= n; i++)
  82.         for (int j = 1; j <= n; j++)
  83.             if (UFS.findf(i) != UFS.findf(j)) {
  84.                 cout << 0 << endl;
  85.                 return 0;
  86.             }
  87.     cout << ans << endl;
  88.     return 0;
  89. }

bzoj1004: [HNOI2008]Cards

居然自己看并1A了这置换群...
首先奇奇怪怪的表述让我们知道出题人要告诉我们是个置换群：

  1. 输入数据保证任意多次洗牌都可用这m种洗牌法中的一种代替——运算封闭；
  2. 置换显然满足结合律、交换律；
  3. 且对每种洗牌法，都存在一种洗牌法使得能回到原状态——每个元素都可逆；
  4. 有没有幺元你加一个不就有了吗？

然后就可以做波利亚计数了。dp预处理每个置换下不变（环内染一种色）的方案数，求和算平均。为了防止重复置换，加一个哈希判重。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 70;
  5. int Sr, Sb, Sg, m, p, n;
  6. int power(int a, int n)
  7. {
  8.     if (n == 0) return 1;
  9.     int k = power(a, n>>1);
  10.     (k *= k) %= p, (k *= (n&1)?a:1) %= p;
  11.     return k;
  12. }
  13. int inv(int a)
  14. { return power(a, p-2); }
  16. int fa[MAXN], siz[MAXN], per[MAXN];
  17. inline int findf(int nd)
  18. { return fa[nd]?fa[nd] = findf(fa[nd]):nd; }
  19. inline void link(int a, int b)
  20. {
  21.     int p = findf(a), q = findf(b);
  22.     if (p != q) fa[p] = q, siz[q] += siz[p];
  23. }
  25. int ht[MAXN], gt = 0;
  26. int dp[MAXN][21][21][21]; // dp嘛..
  27. int cnp = 0; // |G| 波利亚计数原理
  29. // ------
  30. // 哈希表 防止重复而gg
  31. int hsh[3214567];
  32. int hash_p(int p[])
  33. {
  34.     unsigned int val = 0, bs = 1;
  35.     for (int i = 1; i <= n; i++) {
  36.         val += p[i]*bs;
  37.         bs *= (n+1);
  38.     }
  39.     return val%3214567;
  40. }
  41. // ------
  43. int val(int pp[MAXN]) // 计算某一置换下不变的方案数, dp
  44. {
  45.     int k = hash_p(pp);
  46.     if (hsh[k] == 1) return 0;
  47.     else hsh[k] = 1, cnp++;
  48.     memset(fa, 0, sizeof fa);
  49.     for (int i = 1; i <= n; i++) siz[i] = 1;
  50.     for (int i = 1; i <= n; i++) link(i, pp[i]);
  51.     gt = 0;
  52.     for (int i = 1; i <= n; i++)
  53.         if (fa[i] == 0)
  54.             ht[++gt] = siz[i];
  55.     memset(dp, 0, sizeof dp);
  56.     dp[0][0][0][0] = 1;
  57.     for (int i = 1; i <= gt; i++)
  58.         for (int j = 0; j <= Sr; j++)
  59.             for (int k = 0; k <= Sg; k++)
  60.                 for (int l = 0; l <= Sb; l++) {
  61.                     if (j>=ht[i]) (dp[i][j][k][l] += dp[i-1][j-ht[i]][k][l]) %= p;
  62.                     if (k>=ht[i]) (dp[i][j][k][l] += dp[i-1][j][k-ht[i]][l]) %= p;
  63.                     if (l>=ht[i]) (dp[i][j][k][l] += dp[i-1][j][k][l-ht[i]]) %= p;
  64.                 }
  65.     // cout << dp[gt][Sr][Sg][Sb] << endl;
  66.     return dp[gt][Sr][Sg][Sb];
  67. }
  70. int main()
  71. {
  72.     scanf("%d%d%d%d%d", &Sr, &Sg, &Sb, &m, &p);
  73.     n = Sr + Sg + Sb;
  74.     int ans = 0;
  75.     for (int i = 1; i <= n; i++) per[i] = i; // 加个幺元
  76.     (ans += val(per)) %= p;
  77.     for (int i = 1; i <= m; i++) {
  78.         for (int j = 1; j <= n; j++) scanf("%d", &per[j]);
  79.         (ans += val(per)) %= p;
  80.     }
  81.     cout << ans*inv(cnp)%p << endl;
  82.     return 0;
  83. }

1007: [HNOI2008]水平可见直线

水水的半平面交？都是大于号，用一个栈处理就好了，甚至不需要计算几何知识就能脑补1A...五道题打卡下班。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. struct hp {
  5.     double a, b;
  6.     int id;
  7.     hp(){}
  8.     hp(double x, double y, int i):a(x),b(y),id(i){}
  9.     friend bool operator < (const hp &a, const hp &b)
  10.     { return a.a==b.a?a.b>b.b:a.a < b.a; }
  11. } sg[50005];
  12. int n;
  14. stack<int> stk;
  16. int ptw[50005], tp = 0;
  18. bool onleft(const hp &a, const hp &b, const hp &sd)
  19. {
  20.     double x = (b.b-a.b)/(a.a-b.a), y = a.a*x+a.b;
  21.     return y+1e-7 >= sd.a*x+sd.b;
  22. }
  24. int main()
  25. {
  26.     scanf("%d", &n);
  27.     for (int i = 1; i <= n; i++) {
  28.         double a, b;
  29.         scanf("%lf%lf", &a, &b);
  30.         sg[i] = hp(a, b, i);
  31.     }
  32.     sort(sg+1, sg+n+1);
  33.     int nw = n;
  34.     for (int i = 1; i <= n; i++)
  35.         if (sg[i].a == sg[i-1].a) {
  36.             sg[i].a = INT_MAX;
  37.             nw--;
  38.         }
  39.     sort(sg+1, sg+n+1);
  40.     n = nw;
  41.     for (int i = 1; i <= n; i++) {
  42.         // cout << sg[i].id << endl;
  43.         while (stk.size() >= 2) {
  44.             int tp = stk.top(); stk.pop();
  45.             int t2 = stk.top(); stk.pop();
  46.             if (onleft(sg[i], sg[t2], sg[tp])) stk.push(t2);
  47.             else {stk.push(t2), stk.push(tp); break;}
  48.         }
  49.         stk.push(i);
  50.     }
  51.     while (!stk.empty()) ptw[++tp] = sg[stk.top()].id, stk.pop();
  52.     sort(ptw+1, ptw+tp+1);
  53.     for (int i = 1; i <= tp; i++)
  54.         printf("%d ", ptw[i]);
  55.     return 0;
  56. }

bzoj1015: [JSOI2008]星球大战starwar

删除难而加入容易，只要反过来做就好了。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 400005, MAXM = 200005;
  5. struct edge {
  6.     int s, t;
  7. } graph[MAXM];
  8. struct node {
  9.     int to, next;
  10. } edge_list[2*MAXM];
  11. int head[MAXN], top = 0;
  12. inline void push(int i, int j)
  13. { ++top, edge_list[top] = (node) {j, head[i]}, head[i] = top; }
  15. int n, m;
  16. int q[MAXN], l = 0;
  17. int fa[MAXN];
  18. int vis[MAXN], ans[MAXN], cnt, del = 0; // cnt : 联通块个数
  19. inline int findf(int i)
  20. { return fa[i]!=-1?fa[i]=findf(fa[i]):i; }
  21. void link(int i, int j)
  22. {
  23.     int p = findf(i), q = findf(j);
  24.     if (p != q) {
  25.         fa[p] = q;
  26.         cnt--;
  27.     }
  28. }
  29. int main()
  30. {
  31.     memset(fa, -1, sizeof fa);
  32.     memset(head, -1, sizeof head);
  33.     scanf("%d%d", &n, &m);
  34.     for (int i = 1; i <= m; i++) {
  35.         scanf("%d%d", &graph[i].s, &graph[i].t);
  36.         push(graph[i].s, graph[i].t), push(graph[i].t, graph[i].s);
  37.     }
  38.     scanf("%d", &l);
  39.     for (int i = 1; i <= l; i++) scanf("%d", &q[i]), vis[q[i]] = i;
  40.     // for (int i = 1; i <= l; i++) cout << vis[q[i]] << " "; puts("");
  41.     cnt = n;
  42.     for (int i = 1; i <= l; i++) del += vis[q[i]] == i;
  43.     for (int i = 1; i <= m; i++)
  44.         if (!vis[graph[i].s] && !vis[graph[i].t])
  45.             link(graph[i].s, graph[i].t);
  46.     for (int i = l; i >= 1; i--) {
  47.         ans[i] = cnt-del;
  48.         // cout << del << endl;
  49.         if (vis[q[i]] == i) {
  50.             del--;
  51.             vis[q[i]] = 0;
  52.             for (int j = head[q[i]]; j != -1; j = edge_list[j].next) {
  53.                 int to = edge_list[j].to;
  54.                 if (vis[to] == 0)
  55.                     link(q[i], to);
  56.             }
  57.         }
  58.     }
  59.     cout << cnt << endl;
  60.     for (int i = 1; i <= l; i++)
  61.         printf("%d\n", ans[i]);
  62.     return 0;
  63. }

bzoj2242: [SDOI2011]计算器

数论模板题，复习bsgs。
注意bsgs的第二步求逆要在循环外求，否则会被肉眼可见卡常数。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. long long y, z, p;
  5. int t, k;
  6. long long power(long long a, long long n)
  7. {
  8.     if (a == 0) return 0;
  9.     if (n == 0) return 1;
  10.     long long k = power(a, n>>1);
  11.     (k *= k) %= p;
  12.     if (n&1) (k *= a) %= p;
  13.     return k;
  14. }
  15. long long inv(long long a)
  16. { return power(a, p-2); }
  18. map<long long, long long> hsh;
  19. void work()
  20. {
  21.     if (k == 1) {
  22.         printf("%lld\n", power(y, z));
  23.     } else if (k == 2) {
  24.         long long x = inv(y)*z%p;
  25.         if (x > 0 && x*y%p == z%p) printf("%lld\n", x);
  26.         else puts("Orz, I cannot find x!");
  27.     } else {
  28.         y %= p, z %= p;
  29.         if (y == 0 && z == 0) {puts("1");return;}
  30.         if (y == 0) {puts("Orz, I cannot find x!"); return;}
  31.         hsh.clear();
  32.         long long tp = ceil(sqrt(p)+1e-7);
  33.         long long delta = 1;
  34.         for (int i = 1; i <= tp; i++) {
  35.             (delta *= y) %= p;
  36.             if (!hsh.count(delta))hsh[delta] = i;
  37.         }
  38.         long long bs = 1;
  39.         bool fd = 0;
  40.         delta = inv(delta);
  41.         for (int i = 0; i*tp <= p; i++) {
  42.             if (hsh.count(bs*z%p)) {
  43.                 // cout << i*tp << " " << bs << " " << inv(bs) << " " << hsh[inv(bs)] << endl;
  44.                 printf("%lld\n", i*tp+hsh[bs*z%p]);
  45.                 fd = 1;
  46.                 break;
  47.             }
  48.             (bs *= delta) %= p;
  49.         }
  50.         if (!fd) puts("Orz, I cannot find x!");
  51.     }
  52. }
  54. int main()
  55. {
  56.     scanf("%d%d", &t, &k);
  57.     for (int i = 1; i <= t; i++) {
  58.         scanf("%lld%lld%lld", &y, &z, &p);
  59.         work();
  60.     }
  61.     return 0;
  62. }

bzoj1014: [JSOI2008]火星人prefix

一遇数据结构就跪综合症...因为位置和树上位置的转化调了一个多小时。

首先“插入不超过10000个”可以想到是O(lg2n)的插入，就是二分+哈希了。然而哈希是动态的，于是要splay维护。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXM = 2000005;
  5. int chl[MAXM][2];
  6. unsigned long long dat[MAXM], cha[MAXM], power[MAXM];
  7. unsigned int siz[MAXM], fa[MAXM];
  8. int top = 0, root = 0;
  9. inline int new_node(char c, int f)
  10. { return ++top, dat[top] = cha[top] = c-'a'+1, siz[top] = 1, fa[top] = f, top; }
  12. void update(int nd)
  13. {
  14.     siz[nd] = siz[chl[nd][0]] + siz[chl[nd][1]] + 1;
  15.     dat[nd] = dat[chl[nd][0]] + power[siz[chl[nd][0]]]*(cha[nd] + (unsigned long long)27*dat[chl[nd][1]]);
  16. }
  18. void zig(int nd)
  19. {
  20.     // cout << "zigging : " << nd << endl;
  21.     int p = fa[nd], g = fa[fa[nd]], tp = chl[p][0] != nd;
  22.     int tg = chl[g][0] != p, son = chl[nd][tp^1];
  23.     if (son) fa[son] = p; fa[p] = nd, fa[nd] = g;
  24.     if (g) chl[g][tg] = nd;
  25.     else root = nd;
  26.     chl[nd][tp^1] = p, chl[p][tp] = son;
  27.     update(p), update(nd);
  28. }
  30. void dfs(int nd, int tab = 0)
  31. {
  32.     if (!nd) return;
  33.     for (int i = 0; i < tab; i++) cout << " ";
  34.     printf("%d--%c--(%d,%d), siz = %d, fa = %d\n", nd, cha[nd], chl[nd][0], chl[nd][1], siz[nd], fa[nd]);
  35.     dfs(chl[nd][0], tab+2);
  36.     dfs(chl[nd][1], tab+2);
  37. }
  39. void splay(int nd, int tar = 0)
  40. {
  41.     // cout << "splaying : " << nd << " --> son of " << tar << endl;
  42.     while (fa[nd] != tar) {
  43.         // cout << nd << endl;
  44.         int p = fa[nd], g = fa[nd], tp = chl[p][0] != nd, tg = chl[g][0] != p;
  45.         if (fa[p] == tar) {zig(nd); break;}
  46.         if (tp == tg) zig(p), zig(nd);
  47.         else zig(nd), zig(nd);
  48.     }
  49. } // splay tree
  51. int position(int k)
  52. {
  53.     if (k > siz[root] || k <= 0) return 0;
  54.     k--;
  55.     int nd = root;
  56.     while (k != siz[chl[nd][0]]) {
  57.         // cout << nd << " " << k << endl;
  58.         nd = (siz[chl[nd][0]] > k) ? (chl[nd][0]) : (k -= siz[chl[nd][0]]+1, chl[nd][1]);
  59.     }
  60.     return nd;
  61. } // get the position of k-th element
  63. int segment(int l, int r)
  64. {
  65.     int k = position(l-1), p = position(r+1);
  66.     if (l == 1 && r == siz[root]) return root;
  67.     if (l == 1) return splay(p), chl[root][0];
  68.     if (r == siz[root]) return splay(k), chl[root][1];
  69.     return splay(k), splay(p, root), chl[chl[root][1]][0];
  70. } // get a segment [l, r]
  72. unsigned long long query(int l, int r)
  73. { return dat[segment(l, r)]; } // get the hash value in [l, r]
  75. void insert(int k, char c) // push a new element after k-th element
  76. {
  77.     // cout << k << " " << c << " " << siz[root] << endl;
  78.     if (!root && k == 0) {
  79.         root = new_node(c, 0);
  80.         return;
  81.     } // no element
  82.     if (k == 0) {
  83.         splay(position(1));
  84.         chl[root][0] = new_node(c, root);
  85.         update(root);
  86.     } else {
  87.         int nd = segment(k, k);
  88.         // puts("-----"); dfs(root);
  89.         chl[nd][1] = new_node(c, nd);
  90.         while (nd)
  91.             update(nd), nd = fa[nd];
  92.     }
  93.     // dfs(root);
  94. }
  96. void change(int k, char c)
  97. { splay(k), cha[k] = c-'a'+1, update(k);
  98. } // change the value of an existed element
  100. void init()
  101. {
  102.     power[0] = 1;
  103.     for (int i = 1; i < MAXM; i++)
  104.         power[i] = power[i-1]*27;
  105.     // power for hash
  106. }
  107. // -------------
  109. int ask(int opl, int opr)
  110. {
  111.     int len = siz[root]; // maxlen
  112.     int l = 0, r = len-max(opl, opr)+1;
  113.     while (l <= r) {
  114.         int mid = (l+r)>>1;
  115.         if (query(opl, opl+mid-1) == query(opr, opr+mid-1)) l = mid+1;
  116.         else r = mid-1;
  117.     }
  118.     return l-1;
  119. }
  121. int n;
  122. char str[MAXM];
  124. char get_char()
  125. {
  126.     char c;
  127.     do c = getchar(); while(!isalpha(c));
  128.     return c;
  129. }
  131. inline int read() {
  132.     int a = 0, c;
  133.     do c = getchar(); while(!isdigit(c));
  134.     while (isdigit(c)) {
  135.         a = a*10+c-'0';
  136.         c = getchar();
  137.     }
  138.     return a;
  139. }
  141. int main()
  142. {
  143.     init();
  144.     scanf("%s", str);
  145.     for (int i = 0, l = strlen(str); i < l; i++)
  146.         insert(i, str[i]); // build a tree
  147.     n = read();
  148.     int cnt = 0;
  149.     for (int i = 1; i <= n; i++) {
  150.         char c = get_char();
  151.         int l, r, p; char d;
  152.         switch (c) {
  153.             case 'Q':
  154.                 cnt++;
  155.                 l = read(), r = read();
  156.                 printf("%d\n", ask(l, r));
  157.             break;
  158.             case 'R':
  159.                 p = read(), d = get_char();
  160.                 if (!isalpha(d)) throw;
  161.                 change(position(p), d);
  162.             break;
  163.             case 'I':
  164.                 p = read(), d = get_char();
  165.                 if (!isalpha(d)) throw;
  166.                 insert(p, d);
  167.             break;
  168.             default:
  169.                 throw;
  170.             break;
  171.         }
  172.     }
  173.     return 0;
  174. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注