思路： 先整体看成全是0的一个线段树，然后按照题目要求进行修改和查询。
#include <iostream> #include <string.h> #include <string> #include<cstdio> #include <algorithm> #define ll long long using namespace std; ll tree[800010],add[800010]; int a[800010]; int N=0; const int M=2e5+10; void push_up(ll rt) { tree[rt] = tree[rt*2+1] + tree[rt*2+2]; } void push_down(ll rt,ll m) { if(add[rt]) { add[rt*2+1]+=add[rt]; add[rt*2+2]+=add[rt]; tree[rt*2+1]+=(m-(m/2))*add[rt]; tree[rt*2+2]+= (m/2)*add[rt]; add[rt] = 0; } } //板子直接套（注意该树是从节点0开始的） void update_tree(int node,int start,int end,int idx,int val)//点更新 { if(start==end){ a[idx]=val; tree[node]=val; //cout<<"node "<<node<<" "<<start<<" "<<end<<" "<<idx<<endl; } else { int mid=(start+end)/2; int left_node=2*node+1; int right_node=2*node+2; if(idx>=start&&idx<=mid) update_tree(left_node,start,mid,idx,val); else update_tree(right_node,mid+1,end,idx,val); tree[node]=max(tree[left_node],tree[right_node]); // cout<<"node= "<<node<<endl; } } ll query_tree(int L, int R, int l, int r, int rt) //L R 要查询的区间，l r 起始点，tr 根节点0 { if(L <= l && R >= r) return tree[rt]; //push_down(rt,r-l+1); //区间修改特有的一步 ll mid=(l+r)/2; ll left_node=2*rt+1; ll right_node=2*rt+2; ll ans1= -0x3f3f3f,ans2=-0x3f3f3f; if(L <= mid) ans1= query_tree(L, R,l,mid,left_node); if(R > mid) ans2= query_tree(L, R,mid+1,r,right_node); return max(ans1,ans2); } int main() { int m,p; ll tp=0; scanf("%d%d",&m,&p); memset(a,0,sizeof(a)); memset(tree,0,sizeof(tree)); while(m--){ char c; int b; cin>>c>>b; if(c=='Q'){ tp=query_tree( N-b, N-1,0,M, 0); cout<<tp<<endl; } if(c=='A') { N++; ll tp1=(b+tp)%p; update_tree(0,0,M,N-1,tp1); //注意这里的区间是（0~M）M=2e5+10,不是进行添加操作的次数。 } } return 0; }