满满的套路。。。
暴力枚举倍数。。。在主席树上找
还有a[i]会等于0的。。。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; struct chairman_tree { int lc,rc,c; }tr[12000000];int trlen,rt[1100000]; int maketree(int now,int l,int r,int p) { if(now==0) { now=++trlen; tr[now].lc=tr[now].rc=0; tr[now].c=0; } tr[now].c++; if(l==r)return now; else { int mid=(l+r)/2; if(p<=mid)tr[now].lc=maketree(tr[now].lc,l,mid,p); else tr[now].rc=maketree(tr[now].rc,mid+1,r,p); } return now; } int merge(int x,int y) { if(x==0||y==0)return x+y; tr[x].c+=tr[y].c; tr[x].lc=merge(tr[x].lc,tr[y].lc); tr[x].rc=merge(tr[x].rc,tr[y].rc); return x; } //-------------init------------------- int getmax(int x,int y,int l,int r,int ll,int rr) { if(tr[y].c-tr[x].c==0)return 0; if(l==r)return l; int mid=(l+r)/2; if(rr<=mid) return getmax(tr[x].lc,tr[y].lc,l,mid,ll,rr); else if(mid+1<=ll)return getmax(tr[x].rc,tr[y].rc,mid+1,r,ll,rr); else { int d=getmax(tr[x].rc,tr[y].rc,mid+1,r,mid+1,rr); if(d==0) return getmax(tr[x].lc,tr[y].lc,l,mid,ll,mid); else return d; } } int main() { int n,m=2018,Q,x; scanf("%d%d",&n,&Q); trlen=0;memset(rt,0,sizeof(rt)); for(int i=1;i<=n;i++) { scanf("%d",&x); rt[i]=maketree(rt[i],0,m,x); rt[i]=merge(rt[i],rt[i-1]); } int l,r,p; while(Q--) { int ans=0; scanf("%d%d%d",&l,&r,&p);l++;r++; for(int i=0;i<=m;i+=p) { ans=max(ans,getmax(rt[l-1],rt[r],0,m,i+1,min(i+p-1,m))-i); } printf("%d ",ans); } return 0; }