社区讨论
80 MLE on #9#10 求调
P3755[CQOI2017] 老C的任务参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mhjszrcy
- 此快照首次捕获于
- 2025/11/04 08:01 4 个月前
- 此快照最后确认于
- 2025/11/04 08:01 4 个月前
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
const int N=1e5+5;
int n,m,tot1,tot2;
int CNT1,CNT2;
int root,cntX,lc[N*240],rc[N*244],rt[N*244];//
int cntY;
struct node{
int l,r,sum;
}t[N*240];
struct node2{
int a,b,c,d;
}opt[N*8];
int a[N*8],b[N*8];
map<int,int> mp1,mp2;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
void changeY(int &s,int l,int r,int y,int a){
if(!s) s=++cntY;
t[s].sum+=a;
if(l==r) return;
int mid=l+r>>1;
if(y<=mid) changeY(t[s].l,l,mid,y,a);
else changeY(t[s].r,mid+1,r,y,a);
}
void changeX(int &p,int l,int r,int x,int y,int a){
if(!p) p=++cntX;
changeY(rt[p],0,N*4,y,a);
if(l==r) return;
int mid=l+r>>1;
if(x<=mid) changeX(lc[p],l,mid,x,y,a);
else changeX(rc[p],mid+1,r,x,y,a);
}
int askY(int s,int l,int r,int ay,int by){
if(!s) return 0;
if(ay<=l&&r<=by) return t[s].sum;
int mid=l+r>>1,ans=0;
if(ay<=mid) ans+=askY(t[s].l,l,mid,ay,by);
if(by>mid) ans+=askY(t[s].r,mid+1,r,ay,by);
return ans;
}
int askX(int p,int l,int r,int ax,int bx,int ay,int by){
if(!p) return 0;
if(ax<=l&&r<=bx) return askY(rt[p],0,N*4,ay,by);
int mid=l+r>>1,ans=0;
if(ax<=mid) ans+=askX(lc[p],l,mid,ax,bx,ay,by);
if(bx>mid) ans+=askX(rc[p],mid+1,r,ax,bx,ay,by);
return ans;
}
void Hash(){
for(int i=1;i<=tot1;i++)
if(mp1.count(a[i])==0) mp1[a[i]]=++CNT1;
for(int i=1;i<=tot2;i++)
if(mp2.count(b[i])==0) mp2[b[i]]=++CNT2;
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int x,y,k;cin>>x>>y>>k;
a[++tot1]=x,b[++tot2]=y;
opt[i]={x,y,k};
}
for(int i=1;i<=m;i++){
int ax,ay,bx,by;cin>>ax>>ay>>bx>>by;
a[++tot1]=ax,b[++tot2]=ay;
a[++tot1]=bx,b[++tot2]=by;
opt[n+i]={ax,ay,bx,by};
}
sort(a+1,a+tot1+1);
sort(b+1,b+tot2+1);
Hash();
for(int i=1;i<=n;i++){
int x=opt[i].a,y=opt[i].b,k=opt[i].c;
x=mp1[x],y=mp2[y];
changeX(root,0,N*4,x,y,k);
}
for(int i=1;i<=m;i++){
int ax=opt[n+i].a,ay=opt[n+i].b,bx=opt[n+i].c,by=opt[n+i].d;
ax=mp1[ax],bx=mp1[bx],ay=mp2[ay],by=mp2[by];
cout<<askX(root,0,N*4,ax,bx,ay,by)<<'\n';
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...