线段树（模板）

# include
# include
using namespace std;
const int N = 2e5+10;

struct node{
　　int l,r;
　　int v;
}tr[4*N];/*存树，按照4倍储存空间储存*/

/*
线段树的存图形式为顶点为u，他的左儿子为u*2，右儿子为u*2+1
用位运算优化为左儿子：u<<1
右儿子：u<<1|1
*/

void build(int u,int l,int r)/*初始化建图*/
{
　　tr[u] = {l,r};/*顶点u的左右边界为[l,r]*/
　　if(l == r) return;/*如果左右边界相同,也就是说该点为顶点，而不是线段*/
　　int mid = l+r>>1;/*取中点*/
　　build(u<<1,l,mid),build(u<<1|1,mid+1,r);/*分别建立两段线段*/
}

void pushup(int u)/*根据子节点来更新根节点的数据*/
{
　　tr[u].v = max(tr[u<<1].v,tr[u<<1|1].v);/*跟节点的值为左右节点值的最大值*/
}

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;/*取中点，将线段分为[l,mid]，[mid+1,r]两段*/
　　int v = 0;
　　if(l <= mid) v = query(u<<1,l,r);/*如果在左区间则查询左边*/
　　if(r > mid) v = max(v,query(u<<1|1,l,r));/*如果在右边则查询右边的最大值*/

　　return v;
}

void modify(int u,int x,int v)/*单点修改*/
{
　　if(tr[u].l == x && tr[u].r == x) tr[u].v = v;/*如果该节点的左右区间都为X说明这就是要修改的单点*/
　　else

　　{　　/*否则就分两段查询*/
　　int mid = tr[u].l + tr[u].r>>1;
　　if(x <= mid) modify(u<<1,x,v);/*左边就修改左边的点*/
　　　　else modify(u<<1|1,x,v);/*右边则修改右边的点*/
　　pushup(u);/*因为子节点的值被修改，根节点的值有可能被影响，所以需要pushup更新一遍*/
　　}
}

　　int m,p;/*m表示操作次数，p是数据需要%的值*/
　　int main(){
　　　　int n = 0,last = 0;
　　　　cin>>m>>p;
　　　　build(1,1,m);

　　　　int x;
　　　　char op[2];
　　　　while(m--)

　　{
　　　　scanf("%s%d",op,&x);
　　　　if(*op == 'Q')

　　　　{　　/*如果是Q则查询*/
　　　　　　last = query(1,n-x+1,n);
　　　　　　cout< 　　　　}
　　　　else

　　　　{　　/*否则就修改单点的值*/
　　　　　　modify(1,n+1,((long long)last+x)%p);
　　　　　　n++;/*n表示线段的最大长度*/
　　　　}
　　}
　　return 0;
}