对每个询问,单独输出一行,表示al...ar中的逆序对数。

By Autumn

  1 #include <bits/stdc++.h>  2   3 namespace fastRead  4 {  5     inline int nextChar(void)  6     {  7         static const int siz = 1 << 20;  8   9         static char buf[siz]; 10         static char *hd = buf + siz; 11         static char *tl = buf + siz; 12  13         if (hd == tl) 14             fread(hd = buf, 1, siz, stdin); 15  16         return int(*hd++); 17     } 18  19     inline int nextInt(void) 20     { 21         register int ret = 0; 22         register int neg = false; 23         register int bit = nextChar(); 24  25         for (; bit < 48; bit = nextChar()) 26             if (bit == ‘-‘)neg ^= true; 27  28         for (; bit > 47; bit = nextChar()) 29             ret = ret * 10 + bit - ‘0‘; 30  31         return neg ? -ret : ret; 32     } 33 } 34  35 const int mxn = 50005; 36  37 int n, m, h, s[mxn], lastAns = 0; 38  39 namespace chairManTree 40 { 41     const int siz = 1000005; 42  43     int tot; 44     int cnt[siz]; 45     int lsn[siz]; 46     int rsn[siz]; 47  48     int root[mxn]; 49  50     void insert(int &t, int p, int l, int r, int v) 51     { 52         t = ++tot; 53  54         lsn[t] = lsn[p]; 55         rsn[t] = rsn[p]; 56         cnt[t] = cnt[p] + 1; 57  58         if (l != r) 59         { 60             int mid = (l + r) >> 1; 61      62             if (v <= mid) 63                 insert(lsn[t], lsn[p], l, mid, v); 64             else 65                 insert(rsn[t], rsn[p], mid + 1, r, v); 66         } 67     } 68  69     int query(int a, int b, int l, int r, int x, int y) 70     { 71         if (l == x && r == y) 72             return cnt[a] - cnt[b]; 73          74         int mid = (l + r) >> 1; 75  76         if (y <= mid) 77             return query(lsn[a], lsn[b], l, mid, x, y); 78         else if (x > mid) 79             return query(rsn[a], rsn[b], mid + 1, r, x, y); 80         else 81             return query(lsn[a], lsn[b], l, mid, x, mid) + query(rsn[a], rsn[b], mid + 1, r, mid + 1, y); 82     } 83  84     inline void main(void) 85     { 86         for (int i = 1; i <= n; ++i) 87             insert(root[i], root[i - 1], 1, h, s[i]); 88     } 89  90     inline int query(int l, int r, int k) 91     { 92         if (k > 1) 93             return query(root[r], root[l - 1], 1, h, 1, k - 1); 94         else 95             return 0; 96     } 97 } 98  99 namespace binaryInsertTree100 {101     int tree[mxn];102 103     inline void add(int p, int v)104     {105         for (; p <= h; p += p&-p)106             tree[p] += v;107     }108 109     inline int qry(int p)110     {111         int ret = 0;112 113         for (; p >= 1; p -= p&-p)114             ret += tree[p];115 116         return ret;117     }118 119     inline void init(void)120     {121         memset(tree, 0, sizeof(tree));122     }123 }124 125 namespace divideSequence126 {127     const int mxt = 255;128 129     int t, st[mxt], tot, rev[mxt][mxn];130 131     inline int findStart(int k)132     {133         int lt = 1, rt = tot, mid, ans = 0;134 135         while (lt <= rt)136         {137             mid = (lt + rt) >> 1;138 139             if (st[mid] >= k)140                 rt = mid - 1, ans = mid;141             else142                 lt = mid + 1;143         }144 145         return ans;146     }147 148     inline void main(void)149     {150         t = int(sqrt(n) + 0.5);151 152         for (int i = 1, j = 1; i <= n; i += t, ++j)153         {154             st[j] = i;155 156             binaryInsertTree::init();157 158             for (int k = i, sum = 0; k <= n; ++k, ++sum)159             {160                 rev[j][k] = rev[j][k - 1];161                 rev[j][k] += sum - binaryInsertTree::qry(s[k]);162 163                 binaryInsertTree::add(s[k], 1);164             }165 166             tot = j;167         }168     }169 }170 171 namespace preworkHash172 {173     int map[mxn], tot;174 175     inline int find(int k)176     {177         int lt = 1, rt = tot, mid, ans;178 179         while (lt <= rt)180         {181             mid = (lt + rt) >> 1;182 183             if (map[mid] <= k)184                 lt = mid + 1, ans = mid;185             else186                 rt = mid - 1;187         }188 189         return ans;190     }191 192     inline void main(void)193     {194         for (int i = 1; i <= n; ++i)195             map[i] = s[i];196 197         std::sort(map + 1, map + 1 + n);198 199         for (int i = 1; i <= n; ++i)200             if (!tot || map[i] != map[tot])201                 map[++tot] = map[i];202 203         for (int i = 1; i <= n; ++i)204             s[i] = find(s[i]);205 206         h = tot;207     }208 }209 210 inline int solve(int l, int r)211 {212     int id = divideSequence::findStart(l), st, ret;213     214     if (id)215     {216         st = divideSequence::st[id];217         ret = divideSequence::rev[id][r];218     }219     else220         st = r + 1, ret = 0;221 222     if (st > r)223         st = r + 1;224     225     for (int i = l; i < st; ++i)226         ret += chairManTree::query(st, r, s[i]);227     228     binaryInsertTree::init();229 230     for (int i = l, sum = 0; i < st; ++i, ++sum)231     {232         ret += sum - binaryInsertTree::qry(s[i]);233         234         binaryInsertTree::add(s[i], 1);235     }236 237     return ret;238 }239 240 signed main(void)241 {242     n = fastRead::nextInt();243 244     for (int i = 1; i <= n; ++i)245         s[i] = fastRead::nextInt();246 247     preworkHash::main();248 249     chairManTree::main();250 251     divideSequence::main();252 253     m = fastRead::nextInt();254 255     for (int i = 1; i <= m; ++i)256     {257         int l = fastRead::nextInt();258         int r = fastRead::nextInt();259 260         l ^= lastAns;261         r ^= lastAns;262 263         printf("%d\n", lastAns = solve(l, r));264     }265 }