题意：给n,c,k,给n个数字,已知数字都小于c,求一个合法连续数字串的最长长度，合法串要求出现的数字要么出现0次要么就必须出现次数>=k。
思路：从左到右枚举区间右端点，与此同时用线段树维护满足条件的左端点，线段树每个叶节点代表这个节点作为左端点时，所拥有的满足条件的数字个数（如果为C证明这个左端点可取）。从左到右枚举右端点时，判断每个新增的数字，
这个数字对前面的每个左端点拥有的合法数字个数有两点影响：
1.设目前右端点枚举到第i位，这个数字上一次出现的位置为pos，那么在[pos+1,i-1]这个区间内的点作为左端点时，i-1作为右端点时，是没有a[i]这个数字，而i作为右端点出现了a[i],所以[pos+1,i-1]合法个数需要-1.
2.设目前右端点枚举到第i位，这个数字这个数字目前出现记为第一次，往前的第k+1位的位置记为pos,第k位位置记为pos2,需要注意，在[pos+1,pos2]这个区间作为左端点,i-1作为右端点时，a[i]出现了K-1次，而枚举到右端点为i，新增了a[i]后[pos+1,i]这个区间中a[i]出现次数达到k次了，区间内的合法个数需要+1.
对于每次枚举一个右端点，线段树中叶子节点为C的位置就是合法的，[1,i]线性搜索太慢，所以需要线段树记录叶子节点的最大值和最大值的位置，在query时优先查询靠左边的同时满足最大值为C的位置。用vector记录每个数字出现的位置。
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; vector<int> v[maxn]; int n,k,c; struct note { int left,right,maxx,lazy,ans; void up(int val) { maxx+=val; lazy+=val; } } tree[maxn*4]; void pushup(int id) { tree[id].maxx=max(tree[id<<1].maxx,tree[id<<1|1].maxx); if(tree[id].maxx==tree[id<<1].maxx) tree[id].ans=tree[id<<1].ans; else tree[id].ans=tree[id<<1|1].ans; } void pushdown(int id) { if(tree[id].lazy) { tree[id<<1].up(tree[id].lazy); tree[id<<1|1].up(tree[id].lazy); tree[id].lazy=0; } } void build(int id,int l,int r) { tree[id].left=tree[id].ans=l; tree[id].right=r; tree[id].maxx=tree[id].lazy=0; if(l==r) return; int mid=(l+r)/2; build(id<<1,l,mid); build(id<<1|1,mid+1,r); pushup(id); } int query(int id,int l,int r) { if(tree[id].maxx!=c) return -1; if(l<=tree[id].left&&tree[id].right<=r) return tree[id].ans; pushdown(id); int mid=(tree[id].left+tree[id].right)/2; if(r<=mid) return query(id<<1,l,r); else if(l>mid) return query(id<<1|1,l,r); else { int tmp; tmp=query(id<<1,l,mid); if(tmp!=-1) return tmp; else return query(id<<1|1,mid+1,r); } } void update(int id,int l,int r,int val) { if(l<=tree[id].left&&tree[id].right<=r) { tree[id].up(val); return; } pushdown(id); int mid=(tree[id].left+tree[id].right)/2; if(l<=mid) update(id<<1,l,r,val); if(r>mid) update(id<<1|1,l,r,val); pushup(id); } int main() { while(~scanf("%d%d%d",&n,&c,&k)) { for(int i=1; i<=c; i++) { v[i].clear(); v[i].push_back(0); } build(1,1,n); int ans=0; for(int i=1; i<=n; i++) { int x; scanf("%d",&x); update(1,i,i,c-1); if(v[x].back()<i-1) update(1,v[x].back()+1,i-1,-1); v[x].push_back(i); if(v[x].size()>=k+1) { int pos=v[x].size()-k-1; update(1,v[x][pos]+1,v[x][pos+1],1); } int tmp=query(1,1,i); if(tmp!=-1) ans=max(ans,i-tmp+1); } printf("%d\n",ans); } }
#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long const int maxn = 300005 ; const int N = 26 ; int nxt[maxn][N] ;//next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成 int fail[maxn] ;//fail指针，失配后跳转到fail指针指向的节点 int cnt[maxn] ; int num[maxn] ; int len[maxn] ;//len[i]表示节点i表示的回文串的长度 int S[maxn] ;//存放添加的字符 int last ;//指向上一个字符所在的节点，方便下一次add int n ;//字符数组指针 int p ;//节点指针 char a[maxn]; int id[maxn]; const ull hash1=201320111; ull ha[maxn],pp[maxn]; int ans[maxn]; ull getha(int l,int r) { if(l==1) return ha[r]; else return ha[r]-ha[l-1]*pp[r-l+1]; } int check(int l,int r) { int mid=(l+r)/2; if((r-l+1)%2==0) return getha(l,mid)==getha(mid+1,r); return getha(l,mid)==getha(mid,r); } int newnode ( int l ) //新建节点 { for ( int i = 0 ; i < N ; ++ i ) nxt[p][i] = 0 ; cnt[p] = 0 ; num[p] = 0 ; len[p] = l ; return p ++ ; } void init () //初始化 { p = 0 ; newnode ( 0 ) ; newnode ( -1 ) ; last = 0 ; n = 0 ; S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判 fail[0] = 1 ; } int get_fail ( int x ) //和KMP一样，失配后找一个尽量最长的 { while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ; return x ; } void add (int c ) { c -= ‘a‘ ; S[++ n] = c ; int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置 if ( !nxt[cur][c] ) //如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串 { int now = newnode ( len[cur] + 2 ) ;//新建节点 fail[now] = nxt[get_fail (fail[cur])][c] ;//和AC自动机一样建立fail指针，以便失配后跳转 nxt[cur][c] = now ; num[now] = num[fail[now]] + 1 ; } last = nxt[cur][c] ; cnt[last] ++ ; id[last]=n; } void count () { for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ; //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！ for(int i=2; i<p; i++) { if(check(id[i]-len[i]+1,id[i])) ans[len[i]]+=cnt[i]; // for(int j=id[i]-len[i]+1;j<=id[i];j++) // printf("%c",a[j]); // printf(" %d \n",cnt[i]); } } int main() { pp[0]=1; for(int i=1; i<maxn; i++) pp[i]=pp[i-1]*hash1; while(~scanf("%s",a+1)) { int len1=strlen(a+1); for(int i=1; i<=len1; i++) ans[i]=0; ha[0]=0; for(int i=1; i<=len1; i++) ha[i]=ha[i-1]*hash1+a[i]; // printf("%d",check(1,7)); init(); for(int i=1; i<=len1; i++) add(a[i]); count(); for(int i=1; i<=len1; i++) { if(i!=n) printf("%d ",ans[i]); else printf("%d",ans[i]); } printf("\n"); } }
2019 Multi-University Training Contest 2
原文：https://www.cnblogs.com/dongdong25800/p/11575187.html
