【HAOI2017】供给侧改革

【HAOI2017】供给侧改革

题面

题解

// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<cstring>
#include<set>
#include<algorithm>
#include<vector>
#define ri register int
#define N 100500
using namespace std;int n,q,cc;
long long ans[N];
char s[N];struct ques {int l,r,id;bool operator < (const ques &rhs) const {return r<rhs.r || (r==rhs.r && l<rhs.l);}
} qu[N];struct pir{int l,r,v;bool operator < (const pir &rhs) const {return r<rhs.r || (r==rhs.r && l<rhs.l);}
} pp[N<<5];struct SAM{int ch[N<<1][2];int ff[N<<1],len[N<<1];int las,tot;vector<int> son[N<<1];set<int> endp[N<<1];void clear() {las=tot=1;}void extend(int c){int p=las,np=++tot; las=tot;len[np]=len[p]+1;while (p && ch[p][c]==0) ch[p][c]=np,p=ff[p];if (!p) {ff[np]=1;}else {int q=ch[p][c];if (len[q]==len[p]+1) {ff[np]=q;}else {int nq=++tot;len[nq]=len[p]+1; ff[nq]=ff[q];for (ri i=0;i<2;i++) ch[nq][i]=ch[q][i];ff[np]=ff[q]=nq;while (p && ch[p][c]==q) ch[p][c]=nq,p=ff[p];}}endp[np].insert(n-len[np]+1);}void maketree() {for (ri i=1;i<=tot;i++) son[ff[i]].push_back(i);}void merge(int x) {set<int> :: iterator it,it2,itp,itq;for (ri i=0;i<son[x].size();i++) {merge(son[x][i]);if (endp[x].size()<endp[son[x][i]].size()) swap(endp[x],endp[son[x][i]]);for (it=endp[son[x][i]].begin();it!=endp[son[x][i]].end();++it) {endp[x].insert(*it);it2=endp[x].lower_bound(*it);itq=itp=it2;if (itp!=endp[x].begin()) {--itp;pp[++cc]=(pir){*itp,*it,len[x]};}{itq++;if (itq!=endp[x].end()) pp[++cc]=(pir){*it,*itq,len[x]};}endp[x].erase(*it);}for (it=endp[son[x][i]].begin();it!=endp[son[x][i]].end();++it) endp[x].insert(*it);}}
} sam;struct Fenwick{int Max[N<<2],Laz[N<<2];long long Sum[N<<2];int search(int x,int lb,int rb,int l,int r){if (l<=lb && rb<=r) return Max[x];if (lb>r || rb<l) return 0;else {int mid=(lb+rb)/2;return max(search(2*x,lb,mid,l,r),search(2*x+1,mid+1,rb,l,r));}}void in(int x,int lb,int rb,int loc,int v){if (lb==rb) {Max[x]=v;return;}int mid=(lb+rb)/2;if (loc<=mid) in(2*x,lb,mid,loc,v); else in(2*x+1,mid+1,rb,loc,v);Max[x]=max(Max[2*x],Max[2*x+1]);}int xia(int x,int lb,int rb,int v) {if (Max[x]<=v) return 0;if (lb==rb) return lb;int mid=(lb+rb)/2;if (Max[2*x+1]>v) return xia(2*x+1,mid+1,rb,v); else return xia(2*x,lb,mid,v);}int lowerbound(int x,int lb,int rb,int l,int r,int v) {if (l<=lb && rb<=r) return xia(x,lb,rb,v);if (lb>r || rb<l) return 0;int mid=(lb+rb)/2;int t=lowerbound(2*x+1,mid+1,rb,l,r,v);if (t) return t; else return lowerbound(2*x,lb,mid,l,r,v);}void pushdown(int x,int lb,int rb) {int v=Laz[x]; Laz[x]=0;int mid=(lb+rb)/2;Sum[2*x]=(mid-lb+1)*1LL*v,Laz[2*x]=v;Sum[2*x+1]=(rb-mid)*1LL*v,Laz[2*x+1]=v;}void ass(int x,int lb,int rb,int l,int r,int v){if (l<=lb && rb<=r) {Sum[x]=(rb-lb+1)*1LL*v;Laz[x]=v;return;}if (lb>r || rb<l) return;int mid=(lb+rb)/2;if (Laz[x]) pushdown(x,lb,rb);ass(2*x,lb,mid,l,r,v); ass(2*x+1,mid+1,rb,l,r,v);Sum[x]=Sum[2*x]+Sum[2*x+1];}void insert(int loc,int x) {if (search(1,1,n,loc,n)>=x) return;in(1,1,n,loc,x);int Lb=lowerbound(1,1,n,1,loc-1,x);ass(1,1,n,Lb+1,loc,x);}long long find(int x,int lb,int rb,int l,int r) {if (l<=lb && rb<=r) return Sum[x];if (lb>r || rb<l) return 0;else {if (Laz[x]) pushdown(x,lb,rb);int mid=(lb+rb)/2;return find(2*x,lb,mid,l,r)+find(2*x+1,mid+1,rb,l,r);}}
} fg;int main(){scanf("%d %d",&n,&q);sam.clear();scanf("%s",s+1);int l=strlen(s+1);for (ri i=l;i>=1;i--) sam.extend(s[i]-'0');for (ri i=1;i<=q;i++) {scanf("%d %d",&qu[i].l,&qu[i].r);qu[i].id=i;}sam.maketree();cc=0; sam.merge(1);sort(qu+1,qu+q+1);sort(pp+1,pp+cc+1);int p=1;for (ri i=1;i<=q;i++) {while (pp[p].r<=qu[i].r && p<=cc) fg.insert(pp[p].l,pp[p].v),p++;ans[qu[i].id]=fg.find(1,1,n,qu[i].l,qu[i].r);}for (ri i=1;i<=q;i++) printf("%lld\n",ans[i]);return 0;
}

转载于:.html