[JSOI2008]最大数maxnumber 【线段树】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1012
【算法分析】
线段树，会的人都知道。。。
【其它】1Y。用cin果断跑到几乎最慢
【做题原因】邻近省选，练练手，刷出1Y，刷出自信。
【CODE】
#include #include #include #include using namespace std;
const int INF=0x7FFFFFFF;
struct Node{int l,r,key;}Tr[1000000];
int m,mod,n,ans;

void build(int p,int l,int r){
Tr[p].l=l; Tr[p].r=r; Tr[p].key=-INF;
if (l int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}
}

void Add(int p,int t,int key){
if (Tr[p].l==Tr[p].r){
Tr[p].key=key;
return;
}
if (t<=(Tr[p].l+Tr[p].r)/2) Add(p*2,t,key);
else Add(p*2+1,t,key);
Tr[p].key=max(Tr[p*2].key,Tr[p*2+1].key);
}

void Get(int p,int l,int r){
if (l<=Tr[p].l && Tr[p].r<=r){
ans=max(ans,Tr[p].key);
return;
}
int mid=(Tr[p].l+Tr[p].r)/2;
if (l<=mid) Get(p*2,l,r);
if (r> mid) Get(p*2+1,l,r);
}

int main(){
ios::sync_with_stdio(false);
ans=n=0;
cin >> m >> mod;
build(1,1,m);
for (int i=1;i<=m;i++){
char ch; __int64 x;
cin >> ch >> x;
if (ch==’A’){
x=(x+ans)%mod;
n++;
Add(1,n,(int)(x));
}
else{
ans=-INF;
Get(1,n-x+1,n);
cout << ans << "n";
}
}
}