主席树求调
查看原帖
主席树求调
167279
Danno0v0楼主2022/4/2 21:24
#include<bits/stdc++.h>
#define int long long
#define maxx 1<<23
using namespace std;
struct node{int l,r,num;}tree[maxx];
struct poi{int x,y,num;}p[maxx];
int cnt,n,m,root[maxx],s[maxx],tot,size;
bool cmp_1(int x,int y){return x<y;}
bool cmp_2(poi x,poi y){return x.x<y.x;}
void update(int x){tree[x].num=tree[tree[x].l].num+tree[tree[x].r].num;}
int copy(int x)
{
	tree[++cnt]=tree[x];
	return cnt;
}
int build(int x,int l,int r)
{
	x=++cnt;
	if(l==r) return x;
	int m=(l+r)>>1;
	tree[x].l=build(tree[x].l,l,m);
	tree[x].r=build(tree[x].r,m+1,r);
	update(x);
	return x;
}
int insert(int x,int d,int num,int l,int r)
{
	x=copy(x);
	if(l==d&&r==d)
	{
		tree[x].num+=num;
		return x;
	}
	int m=(l+r)>>1;
	if(m>=d) tree[x].l=insert(tree[x].l,d,num,l,m);
	else tree[x].r=insert(tree[x].r,d,num,m+1,r);
	int c=tree[x].num;
	update(x);
	return x;
}
int query(int x,int l_,int r_,int l,int r)
{
	if(l_<=l&&r_>=r) return tree[x].num;
	int mid=(l+r)>>1,ans=0;
	if(mid>=l_) ans+=query(tree[x].l,l_,r_,l,mid);
	if(mid<r_) ans+=query(tree[x].r,l_,r_,mid+1,r);
	return ans;
}
int find(int x)
{
	int l=1,r=size;
	while(l<=r)
	{
		int m=(l+r)>>1;
		if(s[m]==x) return m;
		else if(s[m]>x) r=m-1;
		else l=m+1;
	}
}
int find_more(int x)
{
	int l=1,r=n,ans=-1;
	while(l<=r)
	{
		int m=(l+r)>>1;
		if(s[m]>=x) ans=m,r=m-1;
		else l=m+1;
	}
	return ans;
}
int find_less(int x)
{
	int l=1,r=n,ans=-1;
	while(l<=r)
	{
		int m=(l+r)>>1;
		if(s[m]<=x) ans=m,l=m+1;
		else r=m-1;
	}
	return ans;
}
int find_more_(int x)
{
	int l=1,r=n,ans=-1;
	while(l<=r)
	{
		int m=(l+r)>>1;
		if(p[m].x>=x) ans=m,r=m-1;
		else l=m+1;
	}
	return ans;
}
int find_less_(int x)
{
	int l=1,r=n,ans=-1;
	while(l<=r)
	{
		int m=(l+r)>>1;
		if(p[m].x<=x) ans=m,l=m+1;
		else r=m-1;
	}
	return ans;
}
signed main()
{
	int x1,x2,y1,y2;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y>>p[i].num,s[++tot]=p[i].y;
	sort(s+1,s+tot+1,cmp_1);
	sort(p+1,p+n+1,cmp_2);
	size=unique(s+1,s+tot+1)-s-1;
	for(int i=1;i<=n;i++) p[i].y=find(p[i].y);
	root[0]=build(1,1,size);
	for(int i=1;i<=n;i++) root[i]=insert(root[i-1],p[i].y,p[i].num,1,size);
	for(int i=1;i<=m;i++)
	{
		cin>>x1>>y1>>x2>>y2;
		x1=find_more_(x1),x2=find_less_(x2),y1=find_more(y1),y2=find_less(y2);
		if(x1==-1||x2==-1||y1==-1||y2==-1) cout<<0<<endl;
		else cout<<query(root[x2],y1,y2,1,size)-query(root[x1-1],y1,y2,1,size)<<endl;
	}
}
/*
9 9999
1 1 1
1 3 2
1 5 3
3 1 4
3 3 5
3 5 6
5 1 7
5 3 8
5 5 9
*/

我也不知道为什么是#9#10A然后前面TMWA一大堆……

2022/4/2 21:24
加载中...