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<