CF 1093 GMultidimensional Queries問題解

1786 ワード

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<