//单点修改查询 //http://ybt.ssoier.cn:8088/problem_show.php?pid=1549 //https://www.luogu.com.cn/problem/P1198 //用一维数组来存,当作完全二叉树来存 #include<bits/stdc++.h> using namespace std; const int N=2e5+10; long long int m,p,n,last,t; char op; struct node { int l,r,v; }tr[N*4]; void pushup(int u)//更新每个区间的最大值 { tr[u].v=max(tr[u*2].v,tr[2*u+1].v); } void build(int u,int l,int r)//建立线段树 { tr[u]={l,r}; if(l==r) return; int mid=l+r>>1; build(2*u,l,mid),build(2*u+1,mid+1,r);//向左建立,向右建立 } int query(int u,int l,int r)//查询 { if(tr[u].l>=l&&tr[u].r<=r) return tr[u].v; int mid=tr[u].l+tr[u].r>>1,v=0; if(l<=mid) v=query(2*u,l,r); if(r>mid) v=max(v,query(2*u+1,l,r)); return v; } int modify(int u,int x,int v)//修改 { if(tr[u].l==x&&tr[u].r==x) tr[u].v=v; else{ int mid=tr[u].l+tr[u].r>>1; if(x<=mid) modify(2*u,x,v); else modify(2*u+1,x,v); pushup(u); } } int main() { cin>>m>>p; build(1,1,m); while(m--){ cin>>op>>t; if(op=='Q'){ last=query(1,n-t+1,n); cout<<last<<endl; } else{ modify(1,n+1,(last+t)%p); n++; } } return 0; }
标签:int,线段,tr,mid,build,query,op From: https://www.cnblogs.com/o-Sakurajimamai-o/p/17573099.html