题解 P1198 【[JSOI2008]最大数】

bianyaoyang0419 · 2016-12-25 16:03:59 · 题解

一个小小的线段树就可以AC

···

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct tree
{
    int l,r,_max;
}a[800000];
int n,m,d,x,t,next[200001];
void make_tree(int x,int l,int r)
{
    a[x].l=l;
    a[x].r=r;
    if(l==r)
    {
        next[l]=x;
        return;
    }
    int mid=(l+r)/2;
    make_tree(x*2,l,mid);
    make_tree(x*2+1,mid+1,r);
}
void add(int x)
{
    a[next[++n]]._max=(x+t)%d;
    int temp=next[n];
    while(a[temp]._max>a[temp/2]._max)
    {
        a[temp/2]._max=a[temp]._max;
        temp=temp/2;
    }
}
int q(int x,int y)
{
    if(a[x].l>=y) return a[x]._max;
    if(a[x].r<y) return 0;
    return max(q(x*2,y),q(x*2+1,y));
}
int main()
{
    cin>>m>>d;
    a[1].l=1;
    a[1].r=m;
    make_tree(2,1,(m+1)/2);
    make_tree(3,(m+1)/2+1,m);
    for(int i=1;i<=m;i++)
    {
        char ch;
        cin>>ch;
        cin>>x;
        if(ch=='A') add(x);
        if(ch=='Q')
        {
            t=q(1,n-x+1);
            cout<<t<<endl;
        }
    }
}
···