社区讨论

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 条回复,欢迎继续交流。

正在加载回复...