代码源扫描线权值线段树板子

Bertha 。 2024-03-17 14:51 70阅读 0赞

矩形面积并（存档）

[矩形面积并 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![a357df77b12e4c55a7a0860ea9f61887.png][]

Code（存档，还没写完）：

#include <bits/stdc++.h>
    
    #define y1 Y1
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    
    struct info{
    	int minv,mincnt;
    };
    
    info operator+(const info &l,const info &r){
    	info res;
    	res.minv=min(l.minv,r.minv);
    	if(l.minv==r.minv) res.mincnt=l.mincnt+r.mincnt;
    	else if(l.minv<r.minv) res.mincnt=l.mincnt;
    	else res.mincnt=r.mincnt;
    	return res;
    }
    
    struct Segtree{
    	int t;
    	info val;
    }tree[mxe<<4];
    
    vector<int> Vx;
    vector<array<int,4> > V;
    
    int N;
    int x1,x2,y1,y2;
    
    void pushup(int rt){
    	tree[rt].val=tree[rt<<1].val+tree[rt<<1|1].val;
    }
    void build(int rt,int l,int r){
    	if(l==r){
    		tree[rt]={0,Vx[r]-Vx[r-1]};
    		return;
    	}
    	int mid=l+r>>1;
    	build(rt<<1,l,mid);
    	build(rt<<1|1,mid+1,r);
    	pushup(rt);
    }
    void settag(int rt,int tag){
    	tree[rt].val.minv=tree[rt].val.minv+tag;
    	tree[rt].t=tree[rt].t+tag;
    }
    void pushdown(int rt){
    	if(tree[rt].t){
    		settag(rt<<1,tree[rt<<1].t);
    		settag(rt<<1|1,tree[rt<<1|1].t);
    		tree[rt].t=0;
    	}
    }
    void modify(int rt,int l,int r,int x,int y,int k){
    	if(x<=l&&r<=y){
    		tree[rt].t+=k;
    		tree[rt].val.mincnt+=(r-l+1)*k;
    		return;
    	}
    	pushdown(rt);
    	int mid=l+r>>1;
    	if(x<=mid) modify(rt<<1,l,mid,x,y,k);
    	if(y>mid) modify(rt<<1|1,mid+1,r,x,y,k);
    	pushup(rt);
    }
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++){
    		cin>>x1>>x2>>y1>>y2;
    		Vx.push_back(x1);
    		Vx.push_back(x2);
    		V.push_back({y1,1,x1,x2});
    		V.push_back({y2,-1,x1,x2});
    	}
    	sort(V.begin(),V.end());
    	sort(Vx.begin(),Vx.end());
    	Vx.erase(unique(Vx.begin(),Vx.end()),Vx.end());
    	int m=Vx.size()-1;
    	int last=0;
    	build(1,1,m);
    	int totlen=tree[1].val.mincnt;
    	int ans=0;
    	for(auto it:V){
    		int cov=totlen;
    		if(tree[1].val.minv==0){
    			cov=totlen-tree[1].val.mincnt;
    		}
    		ans+=(it[0]-last)*cov;
    		last=it[0];
    		int x1=lower_bound(Vx.begin(),Vx.end(),it[2])-Vx.begin()+1;
    		int x2=lower_bound(Vx.begin(),Vx.end(),it[3])-Vx.begin();
    		if(x1>x2) continue;
    		modify(1,1,N,x1,x2,it[1]);
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

二维数点

题意：

![7e7d3f1426af49c4b64bd7211f21aa58.png][]

![c9c971b21b684cf686644d847fa55709.png][]

思路：

二维数点本质上也是扫描线，即枚举一个指针，去枚举一棵线段树

在这里，枚举纵坐标，线段树维护一个横坐标区间内有多少点

这道题也用了离线的思想，将询问排序，在维护线段树的同时维护答案数组

具体的看代码就懂

Code：

#include <bits/stdc++.h>
    
    #define y1 Y1
    #define low(x) (x&(-x))
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    
    vector<int> Vx;
    vector<array<int,4> > V;
    
    int N,Q,x,y;
    int x1,x2,y1,y2;
    int ans[mxn],tr[mxn];
    
    void add(int x,int k){
    	for(int i=x;i<=N;i+=low(i)) tr[i]+=k;
    }
    int sum(int x){
    	int res=0;
    	for(int i=x;i;i-=low(i)) res+=tr[i];
    	return res;
    }
    void solve(){
    	cin>>N>>Q;
    	for(int i=1;i<=N;i++){
    		cin>>x>>y;
    		Vx.push_back(x);
    		V.push_back({y,0,x});
    	}
    	for(int i=1;i<=Q;i++){
    		cin>>x1>>x2>>y1>>y2;
    		V.push_back({y1-1,2,x1-1,i});
    		V.push_back({y2,2,x2,i});
    		V.push_back({y2,1,x1-1,i});
    		V.push_back({y1-1,1,x2,i});
    	}
    	sort(V.begin(),V.end());
    	sort(Vx.begin(),Vx.end());
    	Vx.erase(unique(Vx.begin(),Vx.end()),Vx.end());
    	for(auto it:V){
    		if(it[1]==0){
    			int xx=lower_bound(Vx.begin(),Vx.end(),it[2])-Vx.begin()+1;
    			add(xx,1);
    		}else{
    			int xx=upper_bound(Vx.begin(),Vx.end(),it[2])-Vx.begin()+1-1;
    			int t=sum(xx);
    			if(it[1]==1) ans[it[3]]-=t;
    			else ans[it[3]]+=t;
    		}
    	}
    	for(int i=1;i<=Q;i++) cout<<ans[i]<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

区间不同数之和

题意：

![f967c55c644840df86d3dd656c5b20f5.png][]

![43871f50bef34a18b254eebf7dcc890e.png][]

思路：

枚举一个指针，单独考虑每个元素的贡献

对于每个元素都去每个区间更新贡献，这些区间指的是a\[r\]只出现一次的所有区间，同时维护离线了的答案区间

枚举+序列DS=扫描线

Code：

#include <bits/stdc++.h>
    
    #define low(x) (x&(-x))
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    
    vector<pair<int,int> > V[mxn];
    
    int N,Q,l,r;
    int tr[mxn];
    int a[mxn],pre[mxn],ans[mxn];
    
    void add(int x,int k){
    	for(int i=x;i<=N;i+=low(i)) tr[i]+=k;
    }
    int sum(int x){
    	int res=0;
    	for(int i=x;i;i-=low(i)) res+=tr[i];
    	return res;
    }
    void solve(){
    	cin>>N>>Q;
    	for(int i=1;i<=N;i++){
    		cin>>a[i];
    	}
    	for(int i=1;i<=Q;i++){
    		cin>>l>>r;
    		V[r].push_back({l,i});
    	}
    	//枚举一个指针，单独考虑每个元素的贡献
    	//对于每个元素都去每个区间更新贡献，这些区间指的是a[r]只出现一次的所有区间，同时维护离线了的答案区间
    	//枚举+序列DS=扫描线
    	for(int r=1;r<=N;r++){
    		int p=pre[a[r]];
    		add(p+1,a[r]);
    		add(r+1,-a[r]);
    		pre[a[r]]=r;
    		for(auto it:V[r]) ans[it.second]=sum(it.first);
    	}
    	for(int i=1;i<=Q;i++) cout<<ans[i]<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/course/15/problem/688
[a357df77b12e4c55a7a0860ea9f61887.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/303376a1d28b4599969a01d2c0e7e92e.png
[7e7d3f1426af49c4b64bd7211f21aa58.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/5b788b133fe54ec7842c8485db386d6d.png
[c9c971b21b684cf686644d847fa55709.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6a040a89757141379830af186e19999a.png
[f967c55c644840df86d3dd656c5b20f5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/e3a8186f0ac04851ae162b08351d86a6.png
[43871f50bef34a18b254eebf7dcc890e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6ba5c41c65384072bf8a21f4522947de.png