- 1#include < set > 2#include 3#include 4#include 5#include 6#include 7#include < string > 8#include 9#include 10#include 11#include 12#include 13#include 14#define maxn 100010 15 using namespace std;
- 16 struct data {
- 17 int x,
- y,
- z,
- ans1,
- ans2;
- 18
- }
- f[maxn];
- 19 int tree[maxn],
- co[maxn],
- LOL = 0;
- 20 long long ans[maxn];
- 21 int lowbit(int x) {
- return x & -x;
- }
- 22 void add(int p, int v) {
- 23
- for (int i = p; ilowbit(i)) {
- 24
- if (co[i] != LOL) tree[i] = 0;
- 25 co[i] = LOL;
- 26 tree[i] += v;
- 27
- }
- 28
- }
- 29 int find(int p) {
- 30 int ret = -0;
- 31
- for (int i = p; i; i -= lowbit(i)) 32
- if (co[i] == LOL) ret += tree[i];
- 33
- return ret;
- 34
- }
- 35 bool cmpcdq1(const data & a, const data & b) {
- 36
- if (a.y != b.y) return a.y > b.y;
- 37
- else return a.z < b.z;
- 38
- }
- 39 bool cmpcdq2(const data & a, const data & b) {
- 40
- if (a.y != b.y) return a.y < b.y;
- 41
- else return a.z < b.z;
- 42
- }
- 43 void CDQ1(int l, int r) {
- 44
- if (l == r) return;
- 45 int mid = (l + r) >> 1;
- 46 CDQ1(l, mid),
- CDQ1(mid + 1, r);
- 47 sort(f + l, f + mid + 1, cmpcdq1),
- sort(f + mid + 1, f + r + 1, cmpcdq1);
- 48 LOL++;
- 49
- for (int j = mid + 1, i = l; j <= r; j++) {
- 50
- for (; f[i].y > f[j].y && i <= mid; i++) 51 add(f[i].z, 1);
- 52 f[j].ans1 += find(f[j].z);
- 53
- }
- 54
- }
- 55 void CDQ2(int l, int r) {
- 56
- if (l == r) return;
- 57 int mid = (l + r) >> 1;
- 58 CDQ2(l, mid),
- CDQ2(mid + 1, r);
- 59 sort(f + l, f + mid + 1, cmpcdq2),
- sort(f + mid + 1, f + r + 1, cmpcdq2);
- 60 LOL++;
- 61
- for (int j = mid + 1, i = l; j <= r; j++) {
- 62
- for (; f[i].y) 63 add(f[i].z, 1);
- 64 f[j].ans2 += find(f[j].z);
- 65
- }
- 66
- }
- 67 bool cmmp(const data & a, const data & b) {
- 68
- return a.y < b.y;
- 69
- }
- 70 bool cmmmp(const data & a, const data & b) {
- 71
- return a.x < b.x;
- 72
- }
- 73 bool cmmmp1(const data & a, const data & b) {
- 74
- return a.x > b.x;
- 75
- }
- 76 int main() 77 {
- 78 freopen("!.in", "r", stdin);
- 79 freopen("!.out", "w", stdout);
- 80 int n,
- m,
- sp;
- scanf("%d%d", &n, &m);
- 81
- for (int i = 1; i <= n; i++) 82 scanf("%d", &f[i].y),
- f[i].x = i;
- 83 sort(f + 1, f + n + 1, cmmp);
- 84 int cnt = m + 1;
- 85
- for (int i = 1; i <= m; i++) 86 scanf("%d", &sp),
- f[sp].z = cnt,
- cnt--;
- 87
- for (int i = 1; i <= n; i++) 88
- if (!f[i].z) f[i].z = 1;
- 89 sort(f + 1, f + n + 1, cmmmp);
- 90 CDQ1(1, n);
- 91 LOL = 0;
- memset(co, 0, sizeof(co));
- 92 sort(f + 1, f + n + 1, cmmmp1);
- 93 CDQ2(1, n);
- 94
- for (int i = 1; i <= n; i++) 95 ans[f[i].z] += f[i].ans1 + f[i].ans2;
- 96 ans[1] /= 2;
- 97
- for (int i = 2; i <= m + 1; i++) 98 ans[i] += ans[i - 1];
- 99
- for (int i = m + 1; i >= 2; i--) 100 printf("%lld\n", ans[i]);
- 101
- return 0;
- 102
- }
来源: http://www.bubuko.com/infodetail-2005470.html