深夜扫描线求调,快疯了
查看原帖
深夜扫描线求调,快疯了
739757
NOlAKME楼主2023/8/7 00:36
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[100002]; 
int cnt=0,sum=0;
struct tree{
	int l,r,sum,add,num=0;
}t[400009];
map<int,int> mp1;
struct node{
    int a,b,c,d;
    int l,r;
    int h;
}k[100009];
struct st{
    int s,p;
    int l,r;
    int h;
}m[100009];
bool asd(const st l,const st r){
    return l.s<r.s;
}
bool cmp(const node l,const node r){
    return l.b<r.b;
}
//1 2 4 8
void build(int l,int r,int p){
	t[p].l=l;
	t[p].r=r;
	if(l==r){
		t[p].sum=a[l];
		return;
	}
	build(l,(l+r)/2,p*2); 
	build((l+r)/2+1,r,p*2+1);
	t[p].sum=t[p*2].sum+t[p*2+1].sum;
	return;
}
void sp(int p){
    t[p*2].add=t[p].add;
    t[p*2+1].add=t[p].add;
    t[p*2].num=t[p*2].sum*t[p*2].add;
	t[p*2+1].num=t[p*2+1].sum*t[p*2+1].add;
}
void add(int x,int y,int k,int p=1){
	if(x<=t[p].l&&y>=t[p].r){
		if(k) t[p].add=1;
        else t[p].add=0;
		t[p].num=t[p].add*t[p].sum;
		return;
	}
	sp(p);
	int mid=(t[p].l+t[p].r)/2;
	if(x<=mid) add(x,y,k,p*2);
	if(y>mid) add(x,y,k,p*2+1);
	t[p].num=t[p*2].num+t[p*2+1].num;
	return;
}
int ask(int x,int y,int p=1){
	int ans=0;
	//cout<<t[p].num<<endl;
	//cout<<"add:"<<t[p].add<<endl; 
	if(x<=t[p].l&&y>=t[p].r) return t[p].num;
	sp(p);
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid) ans+=ask(x,y,p*2);
	if(y>mid) ans+=ask(x,y,p*2+1);
	return ans; 
}

signed main(){
    int n;
    cin>>n;
	for(int i=1;i<=n;i++){
        int temp1,temp2;//1更小,x
		cin>>temp1>>k[i].b>>temp2>>k[i].d;
        int temp=k[i].b;
        if(k[i].b>k[i].d){
            k[i].b=k[i].d;
            k[i].d=temp;
        }
        if(temp1>temp2){
            temp=temp1;
            temp1=temp2;
            temp2=temp;
        }
        sum++;
        m[sum]={temp1,1};
        m[sum].l=k[i].b;
        m[sum].r=k[i].d;
        sum++;
        m[sum]={temp2,0};
        m[sum].l=k[i].b;
        m[sum].r=k[i].d;
	}
    sort(k+1,k+n+1,cmp);
    for(int i=1;i<=n;i++){
        if(mp1.find(k[i].b)==mp1.end()){
            cnt++;
		    mp1[k[i].b]=cnt;
        }
        if(mp1.find(k[i].d)==mp1.end()){
            cnt++;
		    mp1[k[i].d]=cnt;
        }
	}
    for(int i=1;i<=n*2;i++){
        m[i].l=mp1[m[i].l];
        m[i].r=mp1[m[i].r];
    }
    sort(m+1,m+n*2+1,asd);
    int len=mp1.size()-1;
    int lo=1;
    for(map<int,int>::iterator it=mp1.begin();it!=mp1.end();it++,lo++){
        a[lo]=it->first;
    }
    for(int i=1;i<=len;i++){
        a[i]=a[i+1]-a[i];
        //cout<<a[i]<<' ';
    }
	build(1,len,1);
    //cout<<endl;
    //cout<<ask(1,len)<<endl;
    //cout<<len<<endl;
    int ans=0;
    for(int i=1;i<=2*n;i++){
    	cout<<m[i].l<<' '<<m[i].r-1<<' '<<m[i].p<<endl;
        //add(1,len-1,m[i].p);
        add(m[i].l,m[i].r-1,m[i].p);
        //cout<<m[i].s-m[i-1].s<<endl;
        ans+=ask(1,len)*(m[i].s-m[i-1].s);
    }
    cout<<ans;
    return 0;
}
2023/8/7 00:36
加载中...