why RE?
查看原帖
why RE?
794701
wo_hen_la楼主2024/7/31 21:57
#include <bits/stdc++.h>
using namespace std;

#define sp putchar(' ')
#define en putchar('\n')
#define pb push_back
#define int long long
#define P 998244353
#define HP 1000000000000002097
#define N (int)(4e5+5)

int read(){ char ch=getchar();int x=0,f=1;while(ch>'9' || ch<'0'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return x*f; }
void print(int x){ if(x<0) putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+'0'); }

int n,cnt;
bool vis[N];
vector<int> v;
unordered_map<int,int> mp;
struct node
{
	int num,l,id;
}c[N],d[N];
int a[N],b[N];
bool cmp(node x,node y){ return x.num<y.num; }
int tr[N];
void add(int x,int val)
{
	while(x<=cnt){
		tr[x]+=val;
		x+=x & -x;
	}
}
int query(int x)
{
	int cnt=0;
	while(x){
		cnt+=tr[x];
		x-=x & -x;
	}
	return cnt;
}
main()
{
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		if(!vis[a[i]]) vis[a[i]]=1,v.pb(a[i]),mp[a[i]]=a[i];
		if(!vis[b[i]]) vis[b[i]]=1,v.pb(b[i]),mp[b[i]]=b[i];
	}
	for(int i=1;i<=n;i++) swap(mp[a[i]],mp[b[i]]);
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++){
		c[++cnt].num=mp[v[i]];
		c[cnt].l=1;
		c[cnt].id=cnt;
		if(i!=v.size()-1 && v[i+1]-v[i]>1) c[++cnt].num=v[i]+1,c[cnt].l=v[i+1]-v[i]-1,c[cnt].id=cnt;
	}
	
	sort(c+1,c+1+cnt,cmp);
	for(int i=1;i<=cnt;i++) d[c[i].id].num=i,d[c[i].id].l=c[i].l;
	int ans=0;
//	for(int i=1;i<=cnt;i++) cout<<d[i].l<<" ";
	for(int i=cnt;i>=1;i--){
		add(d[i].num,d[i].l);
		ans+=query(d[i].num-1)*d[i].l;
	}
	cout<<ans;
	return 0;
}

2024/7/31 21:57
加载中...