[BZOJ1012][JSOI2008]最大数maxnumber 线段树

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 typedef long long ll; 6 ll inline readll(){ 7 ????ll Num;char ch; 8 ????while((ch=getchar())<‘0‘||ch>‘9‘);Num=ch-‘0‘; 9 ????while((ch=getchar())>=‘0‘&&ch<=‘9‘) Num=Num*10+ch-‘0‘;10 ????return Num;11 }12 void outll(ll x){13 ????if(x>=10) outll(x/10);14 ????putchar(x%10+‘0‘);15 }16 int mx[200010<<2],len=0;17 #define lson l,mid,rt<<118 #define rson mid+1,r,rt<<1|119 void Pushup(int &rt){20 ????mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);21 }22 void Add(int l,int r,int rt,int pos,int x){23 ????if(l==r){24 ????????mx[rt]=x;25 ????????return;26 ????}27 ????int mid=l+r>>1;28 ????if(pos<=mid) Add(lson,pos,x);29 ????else Add(rson,pos,x);30 ????Pushup(rt);31 }32 int Qry(int l,int r,int rt,int L,int R){33 ????if(l>=L&&R>=r) return mx[rt];34 ????int mid=l+r>>1,ret=0;35 ????if(L<=mid) ret=max(ret,Qry(lson,L,R));36 ????if(R>mid) ret=max(ret,Qry(rson,L,R));37 ????return ret;38 }39 int main(){40 ????int m=readll(),41 ????????d=readll();42 ????char opt[5];43 ????ll t=0,num;44 ????memset(mx,0,sizeof(mx));45 ????for(int i=1;i<=m;i++){46 ????????scanf("%s",opt);47 ????????num=readll();48 ????????if(opt[0]==‘A‘) Add(1,m,1,++len,(num%d+t%d)%d);49 ????????else{50 ????????????t=Qry(1,m,1,len-num+1,len);51 ????????????outll(t);52 ????????????putchar(‘\n‘);53 ????????}54 ????}55 ????return 0;56 }