1 条题解
-
0
#include <bits/stdc++.h> #define int long long using namespace std; const int N=1.5e5+10,LG=__lg(N)+3,inf=1e18; int m,K; struct node{ int x[3]; int val,sum; int ls,rs; int l[3],r[3]; int siz,tag; }t[N],L,R; int rt[LG],cnt=0,n=0,a[N],c; #define ls t[p].ls #define rs t[p].rs void up(int p){ t[p].sum=t[p].val+t[ls].sum+t[rs].sum; t[p].siz=1+t[ls].siz+t[rs].siz; for(int k=0;k<K;k++){ t[p].l[k]=min(t[p].x[k],min(t[ls].l[k],t[rs].l[k])); t[p].r[k]=max(t[p].x[k],max(t[ls].r[k],t[rs].r[k])); } } void down(int p){ if(!t[p].tag) return; int x=t[p].tag; if(ls) t[ls].tag+=x,t[ls].sum+=x*t[ls].siz,t[ls].val+=x; if(rs) t[rs].tag+=x,t[rs].sum+=x*t[rs].siz,t[rs].val+=x; t[p].tag=0; } void release(int &p){ if(!p) return; a[++n]=p; down(p); release(ls); release(rs); p=0; } int build(int l,int r,int k=0){ if(l>r) return 0; int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,[k](int x,int y){ return t[x].x[k]<t[y].x[k]; }); int p=a[mid]; ls=build(l,mid-1,(k+1)%K); rs=build(mid+1,r,(k+1)%K); up(p); return p; } int query(int p){ if(!p) return 0; for(int k=0;k<K;k++) if(L.x[k]>t[p].r[k] || t[p].l[k]>R.x[k]) return 0; bool f=1; for(int k=0;k<K;k++) f&=(L.x[k]<=t[p].l[k] && t[p].r[k]<=R.x[k]); if(f) return t[p].sum; f=1; for(int k=0;k<K;k++) f&=(L.x[k]<=t[p].x[k] && t[p].x[k]<=R.x[k]); down(p); return f*t[p].val+query(ls)+query(rs); } void update(int p){ if(!p) return; for(int k=0;k<K;k++) if(L.x[k]>t[p].r[k] || t[p].l[k]>R.x[k]) return; bool f=1; for(int k=0;k<K;k++) f&=(L.x[k]<=t[p].l[k] && t[p].r[k]<=R.x[k]); if(f){ t[p].tag+=c; t[p].sum+=t[p].siz*c; t[p].val+=c; return; } f=1; for(int k=0;k<K;k++) f&=(L.x[k]<=t[p].x[k] && t[p].x[k]<=R.x[k]); if(f) t[p].val+=c; down(p); update(ls); update(rs); up(p); } #undef ls #undef rs signed main(){ ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin>>K>>m; t[0]={0,0,0,0,0,0,0,inf,inf,inf,0,0,0,0,0}; for(int op,ans=0;m--;){ cin>>op; if(op==1){ cnt++; for(int i=0;i<K;i++) cin>>t[cnt].x[i],t[cnt].x[i]^=ans; cin>>t[cnt].val;t[cnt].val^=ans; a[n=1]=cnt; for(int i=0;i<LG;i++) if(rt[i]) release(rt[i]); else{ rt[i]=build(1,n); break; } } if(op==2){ for(int i=0;i<K;i++) cin>>L.x[i],L.x[i]^=ans; for(int i=0;i<K;i++) cin>>R.x[i],R.x[i]^=ans; cin>>c;c^=ans; for(int i=0;i<LG;i++) update(rt[i]); } if(op==3){ for(int i=0;i<K;i++) cin>>L.x[i],L.x[i]^=ans; for(int i=0;i<K;i++) cin>>R.x[i],R.x[i]^=ans; ans=0; for(int i=0;i<LG;i++) ans+=query(rt[i]); cout<<ans<<"\n"; } } return 0; }
- 1
信息
- ID
- 7197
- 时间
- 5000ms
- 内存
- 64MiB
- 难度
- 10
- 标签
- 递交数
- 4
- 已通过
- 2
- 上传者