非常奇妙的倍增题
题目描述
知名科学家小A在2118年在计算机上实现了模拟聚变的过程。我们将她研究的过程简化。核子共有26种，可以用a到z共26个字母表示。核子聚变的过程可以用一个字符串描述。按照顺序从左到右的顺序，假如有两个相同核子相邻，两个核子就会相互吸引发生聚变生成一个序号+1的核子，特殊的，两个z核子相邻会湮灭没有新的核子生成。每当两个核子聚变时，就需要重新从左到右重复找到两个相邻的相同核子直到不存在为止。比如zyzzy->zyy->zz->小A为了做出足够有效的实验，每次会从一个字符串中选定一个子串操作。她想要知道每次实验这个子串中的核子能否最终全部湮灭。
输入格式
第一行一个只有小写字母的字符串。第二行一个数nn表示询问次数接下来nn行每行两个正整数li,rili,ri表示询问区间
输出格式
对每次询问输出一行Yes或No表示答案
样例输入
yzyyyzyzyyyz
8
1 6
7 12
1 12
6 11
1 1
1 3
4 9
3 8
样例输出
Yes
Yes
Yes
Yes
No
No
No
No
数据规模与约定
L表示字符串长度对于30%的数据满足L<=100
对于60%的数据满足L<=3000,n<=3000
另存在20%数据满足字符串中只存在y,z
对于100%的数据,L<=500000,n<=1000000
题目分析
摘要
第一眼看上去是个数据结构题……但是很明显这题的状态数非常多，并且区间信息也难以合并，所以所有基于序列长度的维护都是要挂的。
这题妙就是在于它用倍增维护基于结果的区间信息。（听上去很高端的样子实际上是不难理解的）
暴力做法
暴力的O(n^2)做法可以得60pts。具体实现可以用栈也可以用链表。
大概就是这个样子。
1 #include<bits/stdc++.h> 2 const int maxn = 8000035; 3 const long long numz = 33554432; 4 5 long long f[maxn]; 6 int pre[maxn],nxt[maxn],head,tail; 7 char ch[maxn]; 8 int n,m,a[maxn],tot; 9 10 int lowbit(int x){return x&-x;} 11 void add(int x, long long c){for (; x<=n; x+=lowbit(x)) f[x]+=c;} 12 long long query(int x) 13 { 14 long long ret = 0; 15 for (; x; x-=lowbit(x)) ret += f[x]; 16 return ret; 17 } 18 bool check(int l, int r) 19 { 20 tot = n, head = l, tail = r; 21 for (int i=l; i<=r; i++) 22 pre[i] = i-1, nxt[i] = i+1; 23 pre[l] = -1, nxt[r] = -1; 24 for (;;) 25 { 26 bool fl = 0; 27 if (head==-1) return 1; 28 if (nxt[head]==-1) return 0; 29 for (int now=head; nxt[now]!=-1; now=nxt[now]) 30 if (a[now]==a[nxt[now]]){ 31 fl = 1; 32 if (a[now]==numz){ 33 int ss = pre[now], tt = nxt[nxt[now]]; 34 if (head==now){ 35 head = tt; 36 if (tt==-1) return 1; 37 pre[tt] = -1; 38 } 39 else{ 40 nxt[ss] = tt; 41 if (tt!=-1) pre[tt] = ss; 42 } 43 }else{ 44 a[++tot] = a[now]*2; 45 int ss = pre[now], tt = nxt[nxt[now]]; 46 if (head==now){ 47 head = tot; 48 if (tt==-1) return 0; 49 pre[tt] = tot, nxt[tot] = tt; 50 } 51 else{ 52 nxt[ss] = tot, pre[tot] = ss, nxt[tot] = tt; 53 if (tt!=-1) pre[tt] = tot; 54 } 55 } 56 break; 57 } 58 if (!fl) return 0; 59 } 60 } 61 int main() 62 { 63 freopen("fusion.in","r",stdin); 64 freopen("fusion.out","w",stdout); 65 scanf("%s",ch+1); 66 n = strlen(ch+1); 67 for (int i=1; i<=n; i++) 68 a[i] = 1<<(ch[i]-'a'), add(i, 1ll*a[i]); 69 scanf("%d",&m); 70 for (int i=1; i<=m; i++) 71 { 72 int l,r; 73 scanf("%d%d",&l,&r); 74 if ((query(r)-query(l-1))%numz==0){ 75 if (check(l, r)) puts("Yes"); 76 else puts("No"); 77 }else puts("No"); 78 } 79 return 0; 80 }
跳一跳？
用nxt[i]表示以i为左端点第一次消完的区间右端点。那么只要预处理出这个nxt[]就可以做到快速查询了————然而查询时也有可能被例如zzzzzzzzz...的数据卡飞，不过对于随机数据已经做得够好了。
先不管zzzzz...的情况，来考虑如何处理nxt[]。
用$t_{i,char}$表示i位置往后第一次遇到char字符的位置，这个是用来处理“聚变”的过程。那么显然这个可以用倍增维护。
处理出$t_{i,char}$之后，nxt[i]就等于$t_{i,z+1}$，这里我们把z聚变后也看做一个虚拟的字符。
再来一个倍增！
既然一维的$nxt[]$会被卡挂，那么同时处理消去好几次后的$nxt[]$（等同于跳了多次）呢？那么nxt[i][j]就表示以i开头消去j次后的位置。
重要的细节
这里有一组数据：xzzxyz
如果只有上面的操作，答案将会是No，因为计算出的结果里第一个x与第二个x是不能接触的。
所以要根据算出的$t_{i,z+1}$更新所有的$t_{i,j}$
1 #include<bits/stdc++.h> 2 #pragma GCC optimize(2) 3 const int maxn = 500035; 4 const int maxLog = 19; 5 const long long numz = 33554432; 6 7 int n,m,s[maxn]; 8 int t[maxn][28],nxt[maxn][20]; 9 char ch[maxn]; 10 11 bool check(int l, int r) 12 { 13 for (int i=maxLog; i>=0; i--) 14 if (nxt[l][i]==r+1) return 1; 15 else if (nxt[l][i]<=r) l = nxt[l][i]; 16 return 0; 17 } 18 void init() 19 { 20 register int i,j; 21 for (i=0; i<=n+2; i++) 22 { 23 for (j=0; j<=26; j++) t[i][j] = n+2; 24 for (j=0; j<=maxLog; j++) nxt[i][j] = n+2; 25 } 26 for (i=n; i>=1; i--) 27 { 28 t[i][s[i]] = i+1; 29 for (j=s[i]+1; j<=26; j++) t[i][j] = t[t[i][j-1]][j-1]; 30 nxt[i][0] = t[i][26]; 31 for (j=0; j<=26; j++) 32 if (t[i][j]==n+2) 33 t[i][j] = t[nxt[i][0]][j]; 34 for (j=1; j<=maxLog; j++) nxt[i][j] = nxt[nxt[i][j-1]][j-1]; 35 } 36 } 37 int main() 38 { 39 register int i,l,r; 40 freopen("fusion.in","r",stdin); 41 freopen("fusion.out","w",stdout); 42 scanf("%s",ch+1); 43 n = strlen(ch+1); 44 for (i=1; i<=n; i++) s[i] = ch[i]-'a'; 45 scanf("%d",&m); 46 init(); 47 for (i=1; i<=m; i++) 48 { 49 scanf("%d%d",&l,&r); 50 if (check(l, r)) puts("Yes"); 51 else puts("No"); 52 } 53 return 0; 54 }
END