离线后以宗教为第一关键字，操作时间为第二关键字排序。

<法一>块状树，线下ac，线上tle……

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;queue
          
           q;int f,c;inline void R(int &x){ c=0;f=1; for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1; for(x=0;c>='0'&&c<='9';c=getchar())(x*=10)+=(c-'0'); x*=f;}void P(int x){ if(x<10)putchar(x+'0'); else{P(x/10);putchar(x%10+'0');}}#define N 100001int en,first[N],next[N<<1],v[N<<1];void AddEdge(const int &U,const int &V){ v[++en]=V; next[en]=first[U]; first[U]=en;}int tops[N],en4;bool delta[N];struct THING{int op,type,x,y,t,p;}th[N*3];bool operator < (const THING &a,const THING &b){return a.type!=b.type ? a.type
          
         
        
       
      
     

<法二>树链剖分+线段树

#include
     
      #include
      
       using namespace std;#define lson rt<<1,l,m#define rson rt<<1|1,m+1,rint f,c;inline void R(int &x){    c=0;f=1;    for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;    for(x=0;c>='0'&&c<='9';c=getchar())(x*=10)+=(c-'0');    x*=f;}void P(int x){    if(x<10)putchar(x+'0');    else{P(x/10);putchar(x%10+'0');}}#define N 100001int en,first[N],next[N<<1],v[N<<1];void AddEdge(const int &U,const int &V){	v[++en]=V;	next[en]=first[U];	first[U]=en;}struct THING{int op,type,x,y,t,p;}th[N*3];bool operator < (const THING &a,const THING &b){return a.type!=b.type ? a.type
       
        siz[son[U]])            son[U]=v[i];        }}void dfs2(int U){    if(son[U])      {        top[son[U]]=top[U];        Num[son[U]]=++tot;        dfs2(son[U]);      }    for(int i=first[U];i;i=next[i])      if(v[i]!=fa[U]&&v[i]!=son[U])        {          top[v[i]]=v[i];          Num[v[i]]=++tot;          dfs2(v[i]);        }}int maxv[N<<2],sumv[N<<2];bool delta[N<<2];void pushdown(const int &rt){	if(delta[rt])	  {	  	delta[rt<<1]=delta[rt<<1|1]=1;	  	maxv[rt<<1]=maxv[rt<<1|1]=sumv[rt<<1]=sumv[rt<<1|1]=0;	  	delta[rt]=0;	  }}void update(int p,int v,int rt,int l,int r){	if(l==r)	  {	  	maxv[rt]=sumv[rt]=v;	  	return;	  }	pushdown(rt);	int m=(l+r>>1);	if(p<=m) update(p,v,lson);	else update(p,v,rson);	sumv[rt]=sumv[rt<<1]+sumv[rt<<1|1];	maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);}int query1(int ql,int qr,int rt,int l,int r){	if(ql<=l&&r<=qr) return sumv[rt];	pushdown(rt);	int m=(l+r>>1),res=0;	if(ql<=m) res+=query1(ql,qr,lson);	if(m
        
         >1),res=0;	if(ql<=m) res=max(res,query2(ql,qr,lson));	if(m
         
          dep[V])      swap(U,V);    return res+query1(Num[U],Num[V],1,1,n);}int Query2(int U,int V){	int f1=top[U],f2=top[V],res=0;	while(f1!=f2)      {        if(dep[f1]
          
           dep[V]) swap(U,V); return max(res,query2(Num[U],Num[V],1,1,n));}int main(){ int A,B; char op[3]; R(n); R(m); for(int i=1;i<=n;++i) { R(w[i]); R(ty[i]); th[i].type=ty[i]; th[i].x=i; th[i].t=i; th[i].y=w[i]; } for(int i=1;i