P3157 [CQOI2011]動態逆序對

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 1e5 + 10;int root[N], ls[N << 8], rs[N << 8], sum[N << 8], cnt;int n, m, pos[N];inline int lowbit(int x) {return x & (-x); }void update(int &rt, int l, int r, int x, int v) {if (!rt) {rt = ++cnt;}sum[rt] += v;if (l == r) {return ;}int mid = l + r >> 1;if (x <= mid) {update(ls[rt], l, mid, x, v);}else {update(rs[rt], mid + 1, r, x, v);} }int A[50], B[50], cnt1, cnt2;int query_sum(int l, int r, int L, int R) {if (l >= L && r <= R) {int ans = 0;for (int i = 1; i <= cnt1; i++) {ans -= sum[A[i]];}for (int i = 1; i <= cnt2; i++) {ans += sum[B[i]];}return ans;}int A1[50], B1[50];int mid = l + r >> 1, ans = 0;if (L <= mid) {for (int i = 1; i <= cnt1; i++) {A1[i] = A[i];A[i] = ls[A[i]];}for (int i = 1; i <= cnt2; i++) {B1[i] = B[i];B[i] = ls[B[i]];}ans += query_sum(l, mid, L, R);for (int i = 1; i <= cnt1; i++) {A[i] = A1[i];}for (int i = 1; i <= cnt2; i++) {B[i] = B1[i];}}if (R > mid) {for (int i = 1; i <= cnt1; i++) {A1[i] = A[i];A[i] = rs[A[i]];}for (int i = 1; i <= cnt2; i++) {B1[i] = B[i];B[i] = rs[B[i]];}ans += query_sum(mid + 1, r, L, R);for (int i = 1; i <= cnt1; i++) {A[i] = A1[i];}for (int i = 1; i <= cnt2; i++) {B[i] = B1[i];}}return ans; }int get_sum(int l, int r, int L, int R) {if (L > R || l > r) {return 0;}cnt1 = cnt2 = 0;for (int j = l - 1; j; j -= lowbit(j)) {A[++cnt1] = root[j];}for (int j = r; j; j -= lowbit(j)) {B[++cnt2] = root[j];}return query_sum(1, n, L, R); }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf("%d %d", &n, &m);for (int i = 1, x; i <= n; i++) {scanf("%d", &x);pos[x] = i;for (int j = i; j <= n; j += lowbit(j)) {update(root[j], 1, n, x, 1);}}ll ans = 0;for (int i = 1; i <= n; i++) {int p = pos[i];ans += get_sum(1, p - 1, i + 1, n);ans += get_sum(p + 1, n, 1, i - 1);}ans >>= 1;for (int i = 1, x; i <= m; i++) {scanf("%d", &x);printf("%lld\n", ans);int p = pos[x];for (int j = p; j <= n; j += lowbit(j)) {update(root[j], 1, n, x, -1);}ans -= get_sum(1, p - 1, x + 1, n);ans -= get_sum(p + 1, n, 1, x - 1);}return 0; }

P3810 三維偏序（陌上花開）

#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;struct Res {int x, y, z;Res(int _x = 0, int _y = 0, int _z = 0) : x(_x), y(_y), z(_z) {} }a[N << 1];int n, m, ans[N];int root[N << 2], ls[N << 9], rs[N << 9], sum[N << 9], cnt;int A[50], cnt1;bool cmp(Res a, Res b) {return a.x < b.x; }inline int lowbit(int x) {return x & (-x); }void update(int &rt, int l, int r, int x, int v) {if (!rt) {rt = ++cnt;}sum[rt] += v;if (l == r) {return ;}int mid = l + r >> 1;if (x <= mid) {update(ls[rt], l, mid, x, v);}else {update(rs[rt], mid + 1, r, x, v);} }int query_sum(int l, int r, int L, int R) {if (l >= L && r <= R) {int ans = 0;for (int i = 1; i <= cnt1; i++) {ans += sum[A[i]];}return ans;}int mid = l + r >> 1, ans = 0, A1[50];if (L <= mid) {for (int i = 1; i <= cnt1; i++) {A1[i] = A[i];A[i] = ls[A[i]];}ans += query_sum(l, mid, L, R);for (int i = 1; i <= cnt1; i++) {A[i] = A1[i];}}if (R > mid) {for (int i = 1; i <= cnt1; i++) {A1[i] = A[i];A[i] = rs[A[i]];}ans += query_sum(mid + 1, r, L, R);for (int i = 1; i <= cnt1; i++) {A[i] = A1[i];}}return ans; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++) {scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);}sort(a + 1, a + 1 + n, cmp);int last = 1;for (int i = 1; i <= n; i++) {for (int j = a[i].y; j <= m; j += lowbit(j)) {update(root[j], 1, m, a[i].z, 1);}if (i == n || a[i].x != a[i + 1].x) {for (int j = last; j <= i; j++) {cnt1 = 0;for (int k = a[j].y; k; k -= lowbit(k)) {A[++cnt1] = root[k];}int res = query_sum(1, m, 1, a[j].z);ans[res - 1]++;}last = i + 1;}}for (int i = 0; i < n; i++) {printf("%d\n", ans[i]);}return 0; }

P3658 [USACO17FEB]Why Did the Cow Cross the Road III P

#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;struct Res {int x, y, z;Res(int _x = 0, int _y = 0, int _z = 0) : x(_x), y(_y), z(_z) {}bool operator < (const Res &t) const {return x < t.x;} }a[N];int l[N], r[N], n, k;int root[N], ls[N << 8], rs[N << 8], sum[N << 8], cnt;int A[50], B[50], cnt1, cnt2;inline int lowbit(int x) {return x & (-x); }void update(int &rt, int l, int r, int x, int v) {if (!rt) {rt = ++cnt;}sum[rt] += v;if (l == r) {return ;}int mid = l + r >> 1;if (x <= mid) {update(ls[rt], l, mid, x, v);}if (x > mid) {update(rs[rt], mid + 1, r, x, v);} }int query_sum(int l, int r, int L, int R) {if (l >= L && r <= R) {int ans = 0;for (int i = 1; i <= cnt1; i++) {ans -= sum[A[i]];}for (int i = 1; i <= cnt2; i++) {ans += sum[B[i]];}return ans;}int mid = l + r >> 1, ans = 0, A1[50], B1[50];if (L <= mid) {for (int i = 1; i <= cnt1; i++) {A1[i] = A[i];A[i] = ls[A[i]];}for (int i = 1; i <= cnt2; i++) {B1[i] = B[i];B[i] = ls[B[i]];}ans += query_sum(l, mid, L, R);for (int i = 1; i <= cnt1; i++) {A[i] = A1[i];}for (int i = 1; i <= cnt2; i++) {B[i] = B1[i];}}if (R > mid) {for (int i = 1; i <= cnt1; i++) {A1[i] = A[i];A[i] = rs[A[i]];}for (int i = 1; i <= cnt2; i++) {B1[i] = B[i];B[i] = rs[B[i]];}ans += query_sum(mid + 1, r, L, R);for (int i = 1; i <= cnt1; i++) {A[i] = A1[i];}for (int i = 1; i <= cnt2; i++) {B[i] = B1[i];}}return ans; }int get_sum(int l, int r, int L, int R) {if (l > r || L > R) {return 0;}cnt1 = cnt2 = 0;for (int i = l - 1; i; i -= lowbit(i)) {A[++cnt1] = root[i];}for (int i = r; i; i -= lowbit(i)) {B[++cnt2] = root[i];}return query_sum(1, n, L, R); }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf("%d %d", &n, &k);for (int i = 1, x; i <= n; i++) {scanf("%d", &x);l[x] = i;}for (int i = 1, x; i <= n; i++) {scanf("%d", &x);r[x] = i;}for (int i = 1; i <= n; i++) {a[i] = Res(l[i], r[i], i);}sort(a + 1, a + 1 + n);long long ans = 0;for (int i = 1; i <= n; i++) {ans += get_sum(a[i].y + 1, n, k + a[i].z + 1, n);ans += get_sum(a[i].y + 1, n, 1, a[i].z - k - 1);for (int j = a[i].y; j <= n; j += lowbit(j)) {update(root[j], 1, n, a[i].z, 1);}}printf("%lld\n", ans);return 0; }

總結

以上是生活随笔為你收集整理的几道偏序问题（数据结构）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。