求调

#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;
}
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\n",ans);
    }
    return 0;
}

图片