[USACO17FEB]Why Did the Cow Cross the Road III G

发布时间：2020-12-14 04:17:52 所属栏目：大数据来源：网络整理

导读：嘟嘟嘟? ? ? ? ? ? ? ? ? ? ? ? ? ? 首先看到这种序列的问题，我就想到了逆序对，然后就想如何把这道题转化。首先要满足这个条件：ai bi。那么我们把所有数按第一次出现的顺序重新赋值，那么对于新的数列，一定满足了ai bi。因为要转换成逆序对，所以先出

嘟嘟嘟? ? ? ? ? ? ? ? ? ? ? ? ?

首先看到这种序列的问题，我就想到了逆序对，然后就想如何把这道题转化。

首先要满足这个条件：ai <bi。那么我们把所有数按第一次出现的顺序重新赋值，那么对于新的数列，一定满足了ai < bi。

因为要转换成逆序对，所以先出现的数赋成更大的值，得到了ai > bi。

接下来的操作都是在新的序列上进行的：像原来求逆序对一样从后往前扫，则扫到的第一个数实际上是该数第二次出现，这时候统计已经出现的比他小的数的个数，那么这些数和它构成的数对满足要求，累加到答案中。然后为了以后的查询，在树状数组上给这个数所在的位置加1。

如果遇到了第二次出现的数，我们就在树状数组上给这个数所在的位置减1，相当于清除这个数，不用来更新答案。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<cctype>
 8 #include<vector>
 9 #include<stack>
10 #include<queue>
11 using namespace std;
12 #define enter puts("") 
13 #define space putchar(‘ ‘)
14 #define Mem(a,x) memset(a,x,sizeof(a))
15 #define rg register
16 typedef long long ll;
17 typedef double db;
18 const int INF = 0x3f3f3f3f;
19 const db eps = 1e-8;
20 const int maxn = 5e4 + 5;
21 inline ll read()
22 {
23     ll ans = 0;
24     char ch = getchar(),last = ‘ ‘;
25     while(!isdigit(ch)) {last = ch; ch = getchar();}
26       while(isdigit(ch)) {ans = ans * 10 + ch - ‘0‘; ch = getchar();}
27       if(last == ‘-‘) ans = -ans;
28       return ans;
29 }
30 inline void write(ll x)
31 {
32       if(x < 0) x = -x,putchar(‘-‘);
33       if(x >= 10) write(x / 10);
34       putchar(x % 10 + ‘0‘);
35 }
36 
37 int n,a[maxn << 1];
38 int id[maxn],cnt = 0;
39 bool vis[maxn];
40 ll ans = 0;
41 
42 int c[maxn];
43 int lowbit(int x)
44 {
45     return x & -x;
46 }
47 void add(int pos,int d)
48 {
49     for(; pos <= n; pos += lowbit(pos)) c[pos] += d;
50 }
51 int query(int pos)
52 {
53     int ret = 0;
54     for(; pos; pos -= lowbit(pos)) ret += c[pos];
55     return ret;
56 }
57 
58 int main()
59 {
60     n = read(); cnt = n;
61     for(int i = 1; i <= (n << 1); ++i) a[i] = read();
62     for(int i = 1; i <= (n << 1); ++i) if(!id[a[i]]) id[a[i]] = cnt--;    //倒序赋值 
63     for(int i = (n << 1); i; --i)
64     {
65         if(!vis[id[a[i]]])
66         {
67             vis[id[a[i]]] = 1;
68             ans += query(id[a[i]]);    
69             add(id[a[i]],1);
70         }
71         else add(id[a[i]],-1);
72     }
73     write(ans),enter;
74     return 0;
75 }

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!