经过一通复杂度分析后发现, 只要暴力做就可以了
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <cstring>
- #include <algorithm>
- #define LL long long
- using namespace std;
- inline LL read()
- {
- LL x = 0, w = 1; char ch = 0;
- while(ch <'0' || ch> '9') {
- if(ch == '-') {
- w = -1;
- }
- ch = getchar();
- }
- while(ch>= '0' && ch <= '9') {
- x = x * 10 + ch - '0';
- ch = getchar();
- }
- return x * w;
- }
- const int MOD = 998244353;
- const int MAXS = 1e7 + 10;
- const int MAXN = 2e5 + 10;
- const int K = 51;
- const int mod = 10233333;
- int n, m;
- char s[MAXS];
- unsigned LL pre[K * 10], g1[K * 10], g2[K * 10];
- int num[MAXN];
- int nex[MAXN], ppr[MAXN];
- void init()
- {
- pre[0] = 1;
- for(int i = 1; i <= K; i++) {
- pre[i] = pre[i - 1] * 19260817;
- }
- }
- int tot = 0;
- struct str {
- unsigned LL x;
- LL num;
- int next;
- } tmp, e[21000000];
- struct hashtable {
- int head[mod];
- void add(unsigned LL x, int k)
- {
- int s = x % mod;
- for(int i = head[s]; i; i = e[i].next) {
- if(e[i].x == x) {
- e[i].num += k;
- return;
- }
- }
- e[++tot].num = k, e[tot].x = x;
- e[tot].next = head[s];
- head[s] = tot;
- }
- LL cal(unsigned LL x)
- {
- int s = x % mod;
- for(int i = head[s]; i; i = e[i].next) {
- if(e[i].x == x) {
- return e[i].num;
- }
- }
- return 0;
- }
- } h;
- inline void merge(int a, int b)
- {
- int l = 0, r = 0;
- for(int i = a; i && l <K; i = ppr[i]) {
- g1[++l] = g1[l - 1] + num[i] * pre[l - 1];
- }
- for(int i = b; i && r < K; i = nex[i]) {
- g2[++r] = g2[r - 1] * 19260817 + num[i];
- }
- for(int i = 1; i <= l; i++) {
- for(int j = 1; j <= r; j++) {
- if(i + j> K)
- break;
- h.add(g1[i] * pre[j] + g2[j], 1);
- }
- }
- nex[a] = b, ppr[b] = a;
- }
- inline void split(int a)
- {
- int b = nex[a];
- int l = 0, r = 0;
- for(int i = a; i && l <K; i = ppr[i]) {
- g1[++l] = g1[l - 1] + num[i] * pre[l - 1];
- }
- for(int i = b; i && r < K; i = nex[i]) {
- g2[++r] = g2[r - 1] * 19260817 + num[i];
- }
- for(int i = 1; i <= l; i++) {
- for(int j = 1; j <= r; j++) {
- if(i + j> K)
- break;
- h.add(g1[i] * pre[j] + g2[j], -1);
- }
- }
- nex[a] = 0, ppr[b] = 0;
- }
- void query()
- {
- int sum = 0;
- scanf("%s", s + 1);
- int k = read();
- int len = strlen(s + 1);
- unsigned LL ha = 0;
- int ans = 1;
- // cout<<k<<endl;
- for(register int i = 1; i <= len; i++) {
- ha = ha * 19260817 + s[i] - '0';
- if(i>= k) {
- // cout<<ha<<" "<<h.cal(ha)<<endl;
- ans = 1ll * ans * h.cal(ha) % MOD;
- // cout<<s[i] - '0'<<""<<(s[i - k + 1] -'0')<<" "<<ha<<endl;
- ha = ha - (s[i - k + 1] - '0') * pre[k - 1];
- }
- }
- printf("%d\n", ans);
- }
- int main()
- {
- // freopen("testdata.in", "r", stdin);
- // freopen("worm.out", "w", stdout);
- init();
- n = read(), m = read();
- for(int i = 1; i <= n; i++) {
- num[i] = read();
- h.add(num[i], 1);
- }
- for(int i = 1; i <= m; i++) {
- int opr = read();
- if(opr == 1) {
- int a = read(), b = read();
- merge(a, b);
- } else if(opr == 2) {
- int a = read();
- split(a);
- } else {
- query();
- }
- }
- }
- /*
- 2 2
- 6 6
- 1 1 2
- 3 666666 4
- */
- View Code
[NOI2017] 蚯蚓排队 - hash + 暴力
来源: http://www.bubuko.com/infodetail-2668576.html