CF 1093 GMultidimensional Queries問題解

CF 1093 GMultidimensional Queries問題解

この問題と同じように、単点修正と区間クエリーが多くなっただけで、どのように維持して、線分の木をセットすればいいです.

#include
#define ll long long
#define lc x<<1
#define rc x<<1|1 
#define re register
#define reg Register
using namespace std;
const int N=2e5+6;
struct xd{
   int z[33],maxs;
   void clr(){memset(z,0,sizeof(z)); maxs=0;}
}p[N],w[N<<2],tmp;
int n,q,k,P,opt,t1,t2,t[7];
inline int read(){
   int T=0,F=1; char ch=getchar();
   while(ch'9'){if(ch=='-') F=-1; ch=getchar();}
   while(ch>='0'&&ch<='9') T=(T<<3)+(T<<1)+(ch-48),ch=getchar();
   return F*T;
}
inline xd pushup(xd u,xd v){
   xd o; o.clr(); o.maxs=max(u.maxs,v.maxs);
   for(int i=0;i
>1;
    build(l,mid,lc),build(mid+1,r,rc);
    w[x]=pushup(w[lc],w[rc]);
}
void update(int l,int r,int u,int x){
    if(l==r){w[x]=tmp; return;}
    int mid=l+r>>1;
    if(u<=mid) update(l,mid,u,lc);
    else update(mid+1,r,u,rc);
    w[x]=pushup(w[lc],w[rc]);
}
xd query(int l,int r,int u,int v,int x){
   if(u<=l&&r<=v) return w[x];
   int mid=l+r>>1;
   if(v<=mid) return query(l,mid,u,v,lc);
   if(u>mid) return query(mid+1,r,u,v,rc);
   return pushup(query(l,mid,u,v,lc),query(mid+1,r,u,v,rc));
}
int main(){
    n=read(),k=read(),P=(1<