20191101 csp-s模拟T2（模拟优化）

T2 元素世界

2.1 题目背景 他已经不记得，自己从哪里出发的了。 他也不知道前方是否真的有光。 但是头马激扬的话语出现了，向着光明。 他能感受到自己的健壮，也能感受到疲惫。 他能感到身旁掠过的嫩草和朔风。 他开始畏惧永恒。

2.2 题目描述 他在冥冥之中感受到了永恒。 他仿佛看到造物主撕开混沌（$\le 26$），用元素${}^{\prime }{a}^{\prime }..{.}^{\prime }{z}^{\prime }$撑起了一个宇宙。 偶然间，一块陆地上的元素能量出现了波动，产生了一条巨大的峡谷。这条峡谷可以看成一个长度为$N$的线段，峡谷的每个单位长度内存在着一种元素。我们定义一个“渊”为这个峡谷的一段连续的区间，两个渊是“相似”的，当且仅当它们含有的元素种类相同且相同元素的个数相同。 拥有扭曲时空力量的探险家来到了这个宇宙，他们此前已经从造物主那里得到了一种操纵元素的方法：“变换”。他们可以指定每种元素分别对应上一种元素对应的元素可以与本身相等，例如元素’${}^{\prime }{a}^{\prime }$可以对应上元素$’z$’；但不同种元素必须对应不同种元素。（例如如果元素$’a’$对应了元素$’c’$，那么元素$’b’,’z’$都不能对应元素$’c’$
，然后将所有元素都变成它们对应的元素。) 现在这些探险家想对这条峡谷进行探索。他们每次会选择这条峡谷的一个渊，并把它记录下来作为标本，他们想知道，这条峡谷有多少个不同渊可能与经过“变换”后的标本相似。 两个渊不同当且仅当它们所代表的区间的左右端点至少有一个不同。

2.3 输入格式 第$1$行一个正整数$T$，表示数据组数。 对于每组数据，第$1$行两个正整数$N,Q$分别表示峡谷长度和询问次数。 第$2$行一个长度为$N$的字符串，表示这个峡谷的状态。 接下来$Q$行，每行两个正整数$L,R$，表示作为标本的渊的左右端点。

2.4 输出格式 对于每组数据，输出$Q$行。 对于每个询问，输出一行一个正整数，表示这条峡谷中可能与经过“变换”后的标本相似的渊的数量。

2.5 输入样例 2 8 4 abccbaba 2 4 3 7 6 6 4 5 2 1 ab 2 2

2.6 输出样例 4 4 8 6 2

2.8 数据范围及约定 对于100%的数据，$1\le T\le 15,1\le N,Q\le 2000,1\le L\le R\le N$且保证峡谷的状态仅由小写字母组成。

思路： 发现两段区间只要元素种类且每种元素的数量的序列相等，那么两序列可以交换。 暴力处理$O(n^3)$。 可加优化： 1.莫队离线处理； 2.滑动窗口将一个$O(n)$变成$O(1)$;

代码：

#include<bits/stdc++.h> using namespace std; #define in Read() #define int long long int in{ int s=0,f=1;char x; for(x=getchar();!isdigit(x);x=getchar()) if(x=='-') f=-1; for( ;isdigit(x);x=getchar()) s=(s<<1)+(s<<3)+(x&15); return s*f; } const int A=1e6+5; int t; int n,q; char x[30005]; int s[A]; struct Qurey{ int l,r,len,ans; int num[50],tot; inline friend bool operator < (const Qurey &x,const Qurey &y){ if(x.len!=y.len) return x.len<y.len; return x.ans<y.ans; } }qur[A]; int ans[A]; int num[50]; int now[50],tot; inline bool comp(const int &a,const int &b){ return a>b; } inline void clean(){ for(int i=1;i<=26;i++) num[i]=0; for(int i=1;i<=q;i++) qur[i].tot=0,ans[i]=0; } signed main(){ t=in; while(t--){ n=in,q=in; clean(); gets(x); for(int i=0;i<n;i++) s[i+1]=x[i]-'a'+1; for(int i=1;i<=q;i++){ qur[i].l=in,qur[i].r=in; qur[i].len=qur[i].r-qur[i].l+1; qur[i].ans=i; for(int j=qur[i].l;j<=qur[i].r;j++) num[s[j]]++; for(int j=1;j<=26;j++) if(num[j]){ qur[i].num[++qur[i].tot]=num[j]; num[j]=0; } sort(qur[i].num+1,qur[i].num+1+qur[i].tot,comp); } sort(qur+1,qur+1+q); for(int i=1;i<=q;i++){ int j=i; while(qur[j+1].len==qur[j].len) j++; for(int k=1;k<=qur[i].len;k++) num[s[k]]++; for(int k=1;k<=26;k++) if(num[k]) now[++tot]=num[k]; sort(now+1,now+1+tot,comp); for(int k=i;k<=j;k++){ if(qur[k].tot!=tot) continue; bool bz=0; for(int u=1;u<=tot;u++) if(qur[k].num[u]!=now[u]){ bz=1; break; } if(bz==1) continue; ans[qur[k].ans]++; } for(int k=qur[i].len+1;k<=n;k++){ int u=k-qur[i].len,v=k; sort(now+1,now+1+tot); int w; if(num[s[v]]){ for(int aa=1;aa<=tot;aa++) if(now[aa]==num[s[v]]) w=aa; now[w]++; num[s[v]]++; } else{ now[++tot]=1; num[s[v]]++; } int wj; for(int aa=1;aa<=tot;aa++) if(now[aa]==num[s[u]]) wj=aa; now[wj]--; num[s[u]]--; sort(now+1,now+1+tot,comp); while(!now[tot]&&tot>=0) tot--; for(int k=i;k<=j;k++){ if(qur[k].tot!=tot) continue; bool bz=0; for(int u=1;u<=tot;u++) if(qur[k].num[u]!=now[u]){ bz=1; break; } if(bz==1) continue; ans[qur[k].ans]++; } } i=j; for(int k=1;k<=26;k++) num[k]=0; tot=0; } for(int i=1;i<=q;i++) printf("%lld\n",ans[i]); } return 0; }