C++14(g++5.4) 解法, 执行用时: 104ms, 内存消耗: 3684K, 提交时间: 2018-08-06 10:59:14

#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<algorithm>
#include<map>
#include<utility>
#include<algorithm>
using namespace std;
#define ll long long
#define mp make_pair
#define X first
#define Y second
const int N=100008;
const ll M=998244353ll;
int n,b[N];
pair<int,int>a[N];
map<int,int>f;
int add(int x,int y){while(x<=n){b[x]+=y;x+=x&(-x);}return 0;}
int sum(int x){int y=0;while(x>0){y+=b[x];x-=x&(-x);}return y;}
int main(void)
{
	int i,j,k;ll ans=0;
	scanf("%d",&n);
	ans=(n+(0ll+n)*(n-1)/2)%M;
	for(i=1;i<=n;i++)scanf("%d%d",&a[i].X,&a[i].Y);
	f.clear();for(i=1;i<=n;i++)f[a[i].Y]++;
	for(auto p:f)ans=((ans-(p.Y+0ll)*(p.Y-1)/2)%M+M)%M;
	for(i=1;i<=n;i++){b[i]=a[i].Y;}sort(b+1,b+1+n);
	for(i=1;i<=n;i++)a[i].Y=lower_bound(b+1,b+1+n,a[i].Y)-b;
	sort(a+1,a+1+n);
	for(i=1;i<=n;i++)b[i]=0;
	for(i=n;i>=1;i=j)
	{
		for(j=i;j>=1&&a[j].X==a[i].X;j--);
		for(k=j+1;k<=i;k++)ans=(ans+(0ll+sum(a[k].Y-1))*(0ll+sum(n)-sum(a[k].Y)))%M;
		for(k=j+1;k<=i;k++)add(a[k].Y,1);
	}
	cout<<(ans%M+M)%M;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 107ms, 内存消耗: 2532K, 提交时间: 2018-08-02 14:25:18

#include <bits/stdc++.h>
#define MAXN 100010
using namespace std;
const int mod = 998244353;
struct node{
	int x,y;
}a[MAXN];
int n,b[MAXN],c[MAXN],t[MAXN<<2];

bool cmp1(const node&x,const node&y)
{
	return x.x>y.x;
}

void add(int p,int x)
{
	while(p<=n){
		t[p]+=x;
		p+=p&-p;
	}
}

int sum(int p)
{
	int res=0;
	while(p){
		res+=t[p];
		p-=p&-p;
	}
	return res;
}

int main()
{
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
		b[i]=a[i].y;
	}
	sort(b+1,b+n+1);
	for(i=1;i<=n;i++){
		a[i].y=lower_bound(b+1,b+n+1,a[i].y)-b;
		c[a[i].y]++;
	}
	sort(a+1,a+n+1,cmp1);
	a[n+1].y=-1;
	int pre=1;
	long long ans=n+1ll*n*(n-1)/2;
	for(i=1;i<=n;i++) ans-=1ll*c[i]*(c[i]-1)/2;
	ans%=mod;

	for(i=1;i<=n;i++){
		int up=sum(a[i].y-1);
		int down=sum(n)-sum(a[i].y);
		ans+=1ll*up*down;
		ans%=mod;
		if(a[i].x!=a[i+1].x){
			for(pre;pre<=i;pre++) add(a[pre].y,1);
		}
	}
	printf("%lld\n",ans);
 return 0;
}