https://www.nowcoder.com/acm/contest/143/I
vc-dimension
题解：分三种情况，组合数学算一下，其中一种要用树状数组维护
技巧（来自UESTC）：1.循环技巧i主j滑
2.树状数组：一个数列从左到右分别维护某个元素左边比它大num的与右边比他大的num时，从上往下扫， 对每个点的x坐标离散化累加1到X轴上，然后就会发现sum(p[i].x-1)就是左边比它大的，i-1-sum(p[i])就是右边比它大的。 注意y相同的点，需要一起更新（我已开始一个一个更新，根本写不出来）
orz太屌了
坑点：我循环写错了+公式里i,j写反了，wa了20发
比赛时x,y轴都看反了orz
#define _CRT_SECURE_NO_WARNINGS #include<cmath> #include<iostream> #include<stdio.h> #include<algorithm> #include<cstring> #include<stack> #include<vector> #include<string.h> #include<queue> #include<string> #include<set> using namespace std; #define rep(i,t,n) for(int i =(t);i<=(n);++i) #define per(i,n,t) for(int i =(n);i>=(t);--i) #define mmm(a,b) memset(a,b,sizeof(a)) #define eps 1e-6 #define pb push_back #define lowbit(x) ((x)&(-(x))) const int maxn = 3e5 + 5; const int inf = 1e7 + 5;//0x7fffffff; //无限大 const int MOD = 1013; typedef long long ll; const int mod = 998244353; int power(int a, int b) { int c = 1; a %= mod; while (b) { if (b & 1) c = 1ll * c*a%mod; a = 1ll * a*a%mod; b >>= 1; } return c; } struct node { int x, y; void sc() { scanf("%d%d", &x, &y); } }p[maxn]; int n; bool cmp(node a, node b) { return a.x > b.x; } bool cmpy(node a, node b) { return a.y < b.y; } int f[maxn]; int idx; void add(int x, int y) { for (; x <= idx; x += lowbit(x)) f[x] += y; } int sum(int x) { int ans = 0; for (; x; x -= lowbit(x)) ans += f[x]; return ans; } int main() { int div2 = power(2, mod - 2); cin >> n; rep(i, 1, n) { p[i].sc(); } int ans = n; ans += 1ll*n * (n - 1)%mod*div2 % mod; if (ans >= mod)ans -= mod; else if (ans < 0)ans += mod; sort(p + 1, p + 1 + n, cmpy); idx = 0; for (int i = 1, j; i <= n; i = j + 1) { for (j = i ; j < n&&p[i].y == p[j+1].y; j++); ++idx; rep(k, i, j)p[k].y = idx; ans -=1ll* (j - i)*(j - i + 1)%mod*div2%mod; if (ans >= mod)ans -= mod; else if (ans < 0)ans += mod; } mmm(f, 0); sort(p + 1, p + 1 + n, cmp); for (int i = 1, j; i <= n; i = j + 1) { for (j = i ; j < n&&p[i].x == p[j+1].x; j++); rep(k, i, j) { int t1 = sum(p[k].y - 1); int t2 = i - 1 - sum(p[k].y); ans += 1ll * t1*t2%mod; if (ans >= mod)ans -= mod; else if (ans < 0)ans += mod; } rep(k, i, j)add(p[k].y, 1); } cout << ans << endl; cin >> n; return 0; } /* */
一开始无脑分别前后维护
#define _CRT_SECURE_NO_WARNINGS #include<cmath> #include<iostream> #include<stdio.h> #include<algorithm> #include<cstring> #include<stack> #include<vector> #include<string.h> #include<queue> #include<string> #include<set> using namespace std; #define rep(i,t,n) for(int i =(t);i<=(n);++i) #define per(i,n,t) for(int i =(n);i>=(t);--i) #define mmm(a,b) memset(a,b,sizeof(a)) #define eps 1e-6 #define pb push_back const int maxn = 1e5 + 5; const int inf = 1e7 + 5;//0x7fffffff; //无限大 const int MOD = 1013; typedef long long ll; const long long mod = 998244353; int power(int a,int b){ int c=1; a%=mod; while (b) { if (b&1) c=1ll*c*a%mod; a=1ll*a*a%mod; b>>=1; } return c; } ll div2 = power(2, mod - 2); struct node { int x, y; int id; void sc() { scanf("%d%d", &x, &y); } }P[maxn]; ll n; bool cmp(node a, node b) { if (a.x != b.x) return a.x < b.x; else return a.y < b.y; } bool cmpx(node a, node b) { if (a.x != b.x) return a.x > b.x; else return a.y < b.y; } bool cmpy(node a, node b) { return a.y < b.y; } int cnt[maxn]; ll l[maxn], r[maxn]; int d[maxn]; int lowbit(int x) { return x & (-x); } int fr[maxn], bk[maxn]; void add(int x, int v) {//a[x]+=v; while (x <= maxn) { d[x] += v; x += lowbit(x); } } int query(int x) { int res = 0; while (x) { res += d[x]; x -= lowbit(x); } return res; } int main() { cin >> n; rep(i, 1, n) { P[i].sc(); P[i].id = i; } sort(P + 1, P + n + 1, cmp); int idx = 0; int now = 0; rep(i, 1, n) { if (P[i].x != now) { cnt[++idx]++; now = P[i].x; } else { cnt[idx]++; } } ll ans = n; ll tmp = n * (n - 1) %mod*div2; rep(i, 1, idx)if (cnt[i] > 1) { tmp = (tmp - cnt[i] * (cnt[i] - 1) % mod *div2) % mod; } ans = (ans + tmp) % mod; //维护每个点左右比它高的点 sort(P + 1, P + n + 1, cmpy); idx = 0; now = 0; rep(i, 1, n) { if (P[i].y != now) { P[i].y = ++idx; now = P[i].y; } else { P[i].y = idx; } } sort(P + 1, P + n + 1, cmp); now = 0; rep(i, 1, n) { if (P[i].x != P[i - 1].x)fr[i] =now= i - 1; else fr[i] = now; } now = 0; per(i, n, 1) { if (P[i].x != P[i + 1].x)bk[i] = now = i + 1; else bk[i] = now; } rep(i, 1, n) { if(P[i].x!=P[i-1].x)l[i] =ll( i-1-query(P[i].y)); else { if (P[i].y >= P[fr[i]].y || P[i].y >= P[bk[i]].y)l[i] = 0; else l[i] = l[i - 1]; } add(P[i].y, 1); } mmm(d, 0); //sort(P + 1, P + n + 1, cmpx); int first = 1; per(i, n, 1) { if (P[i].x != P[i + 1].x)r[i] = ll(n-i - query(P[i].y)),first=1; else { if (P[i].y >= P[fr[i]].y || P[i].y >= P[bk[i]].y)r[i] = 0; else { if (first) { first = 0; r[i] = ll(n - i -1- query(P[i].y)); } else r[i] = r[i + 1]; } } add(P[i].y, 1); } tmp = 0; rep(i, 1, n) { tmp = (tmp + l[i] * r[i] % mod) % mod; } ans = (ans + tmp) % mod; cout << ans<<endl; //sort(P + 1, P + n + 1, cmp); rep(i, 1, n) { //cout << l[i] << ' ' << r[i] << endl; } cin >> n; } /* */