voidquicksort(int l, int r){ if (l >= r) return; int i = l, j = r, base = a[l]; //取最左边的数为基准数(取哪个都行); while (i < j) { while (i < j && a[j] >= base) j--; //找到右起第一个小于基准数的数 while (i < j && a[i] <= base) i++; //找到左起第一个大于基准数的数 if (i < j) swap(a[i], a[j]); //交换两数 } swap(a[l], a[i]); //把基准数换到中心 此时[l,r]内基准数左边的所有数小于基准数 基准数右边的所有数大于基准数 quicksort(l, i - 1); quicksort(i + 1, r); //分别向左右递归 }
inlinevoidadd(ll x){ cnt[x]++; if (cnt[x] > 1) ans = ans - (cnt[x]-1) * (cnt[x]-2) + (cnt[x]) * (cnt[x]-1); }
inlinevoiddel(ll x){ cnt[x]--; if (cnt[x] > 0) ans = ans - (cnt[x]) * (cnt[x]+1) + (cnt[x]-1) * (cnt[x]); }
inlinevoidupdate(ll l, ll r){ while (nl < l) del(c[nl++]); while (nl > l) add(c[--nl]); while (nr < r) add(c[++nr]); while (nr > r) del(c[nr--]); }
inlinevoidgetans(ll x, ll y, ll id){ if (x == 0) { ansx[id] = 0; ansy[id] = 1; return; } ll gcd = __gcd(x, y); x /= gcd; y /= gcd; ansx[id] = x; ansy[id] = y; }
intmain(){ n = read(); m = read(); bl = sqrt(n); for (ll i = 1; i <= n; i++) { c[i] = read(); } for (ll i = 1; i <= m; i++) { q[i].l = read(); q[i].r = read(); q[i].id = i; } sort(q+1, q+m+1, cmp); nl = q[1].l, nr = q[1].r; for (ll i = q[1].l; i <= q[1].r; i++) { add(c[i]); } getans(ans, (nr-nl+1)*(nr-nl), q[1].id); for (ll i = 2; i <= m; i++) { update(q[i].l, q[i].r); getans(ans, (nr-nl+1)*(nr-nl), q[i].id); } for (ll i = 1; i <= m; i++) { printf("%lld/%lld\n", ansx[i], ansy[i]); } return0; }
由此可以看出 通过排序改变询问顺序有时候可以辅助解题
排序也经常用于数据离散化
感觉扯得有点多了 跑题了
2.逆序对
逆序对定义为序列$a[1\dots n]$中的一对下标$(i,j)$满足$1\le i < j \le n$且$a[i] > a[j]$。逆序对和排序算法有着密切关系。
inlineintread(){ int x = 0, f = 1; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1; for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0'); return x * f; }
int t, n, m, k, a[100005], srt[100005], mx, tp[100005], le[100005], ri[100005], tmp[100005];
namespace Segtree{ //线段树自己写去 }
usingnamespace Segtree;
boolcheck(int x){ for (int i = 1; i <= n; i++) tmp[i] = (a[i] >= x); build(1, 1, n); for (int i = 1; i <= m; i++) { int num = query(1, le[i], ri[i]); if (!tp[i]) { update(1, le[i], ri[i]-num, 0); update(1, ri[i] - num + 1, ri[i], 1); } else { update(1, le[i], le[i] + num - 1, 1); update(1, le[i] + num, ri[i], 0); } } return query(1, k, k) == 1; }
intmain(){ t = read(); while (t--) { n = read(); m = read(); for (int i = 1; i <= n; i++) a[i] = srt[i] = read(); for (int i = 1; i <= m; i++) tp[i] = read(), le[i] = read(), ri[i] = read(); k = read(); sort(srt+1, srt+n+1); mx = unique(srt+1, srt+n+1)-srt-1; for (int i = 1; i <= n; i++) a[i] = lower_bound(srt+1, srt+mx+1, a[i])-srt; int l = 1, r = mx, mid, ans = 0; while (l <= r) { mid = (l + r) >> 1; if (check(mid)) { ans = mid; l = mid + 1; } else r = mid - 1; } printf("%d\n", srt[ans]); } return0; }
#include<bits/stdc++.h> #define mod 1000000007 usingnamespacestd; typedeflonglong ll;
inlineintread(){ int x = 0, f = 1; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1; for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0'); return x * f; }
int n, m, l[30], r[30]; ll dp[2000005], wa, tot; bool ok[2000005];
inlinevoidgetnum(int x, int *num){ for (int i = 1; i <= n; i++) { num[i] = (x >> (n - i)) & 1; } }
inline ll fpow(ll x, ll t){ ll ret = 1; for (; t; x = x * x % mod, t >>= 1) if (t & 1) ret = ret * x % mod; return ret; }
inlineboolcheck(int x){ int num[30] = {0}; getnum(x, num); for (int i = 1; i <= m; i++) { if (num[l[i]] > num[r[i]]) swap(num[l[i]], num[r[i]]); } for (int i = 2; i <= n; i++) { if (num[i] < num[i-1]) { returnfalse; } } returntrue; }
intmain(){ n = read(); m = read(); for (int i = 1; i <= m; i++) { l[i] = read(); r[i] = read(); } for (int i = 0; i <= (1 << n) - 1; i++) { ok[i] = check(i); } dp[0] = tot = 1; for (int i = 1; i <= n; i++) tot = tot * i % mod; for (int i = 1; i <= (1 << n) - 1; i++) { if (!ok[i]) continue; for (int j = 1; j <= n; j++) { if (i & (1 << (j-1))) { dp[i] = (dp[i] + dp[i-(1<<(j-1))]) % mod; } } } wa = (tot - dp[(1<<n)-1] + mod) % mod; printf("%lld\n", wa * fpow(tot, mod-2) % mod); return0; }
inlineintread(){ int x = 0, f = 1; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1; for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0'); return x * f; }
int n, m, q; int a[1505], b[1505], posa[1505], posb[1505], le[1000005], ri[1000005]; set<int> s;
voidmy_sort(){ for (int j = m; j >= 1; j--) { int pos = 0; set<int>::iterator it; do { it = s.lower_bound(le[j]); pos = *it; if (it == s.end() || pos >= ri[j]) break; swap(a[pos], a[pos+1]); s.erase(pos); if (pos >= 2) { if (a[pos-1] >= a[pos]) { s.erase(pos-1); } else { s.insert(pos-1); } } if (pos <= n - 2) { if (a[pos+1] >= a[pos+2]) { s.erase(pos+1); } else { s.insert(pos+1); } } } while (1); } }
structSegtree{ structsegtree{ int l, r, mn, tag; } tr[100005]; #define lson ind<<1 #define rson ind<<1|1 voidbuild(int ind, int l, int r){ tr[ind].l = l, tr[ind].r = r, tr[ind].tag = 0, tr[ind].mn = 0; if (l == r) { return; } int mid = (l + r) >> 1; build(lson, l, mid); build(rson, mid+1, r); } voidpushdown(int ind){ if (!tr[ind].tag) return; int v = tr[ind].tag; tr[ind].tag = 0; tr[lson].mn += v; tr[rson].mn += v; tr[lson].tag += v; tr[rson].tag += v; } voidupdate(int ind, int x, int y, int v){ int l = tr[ind].l, r = tr[ind].r; if (x <= l && r <= y) { tr[ind].mn += v; tr[ind].tag += v; return; } pushdown(ind); int mid = (l + r) >> 1; if (x <= mid) update(lson, x, y, v); if (mid < y) update(rson, x, y, v); tr[ind].mn = min(tr[lson].mn, tr[rson].mn); } }T;
pair<int, int> tmp[1505];
inlinevoidinit(){ for (int i = 1; i <= n; i++) tmp[i] = make_pair(b[i], i); sort(tmp+1, tmp+n+1); for (int i = 1; i <= n; i++) b[tmp[i].second] = i; for (int i = 1; i <= n; i++) posb[b[i]] = i; }
intmain(){ n = read(); m = read(); q = read(); for (int i = 1; i <= m; i++) { le[i] = read(); ri[i] = read(); } for (int i = 1; i <= n; i++) a[i] = i; for (int i = 1; i < n; i++) s.insert(i); my_sort(); for (int i = 1; i <= n; i++) posa[a[i]] = i; for (int i = 1; i <= q; i++) { for (int j = 1; j <= n; j++) b[j] = read(); init(); T.build(1, 1, n); bool ok = 1; for (int j = 2; j <= n; j++) { T.update(1, posb[j-1], n, 1); T.update(1, posa[j-1], n, -1); if (T.tr[1].mn < 0) { ok = 0; break; } } if (ok) puts("Accepted"); elseputs("Wrong Answer"); } return0; }