数状数组

1.循环右移，老套路了，直接开2n数组

然后利用树状数组进行区间求和和单点修改,每次减去之前以及出现过的值

Problem - E - Codeforces

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 1e6 + 10;
 5 
 6 int t;
 7 int c[N * 2];
 8 int sum(int x)
 9 {
10     int res = 0;
11      while(x){
12          res += c[x];
13          x -= x & -x;
14      }
15      return res;
16 } 
17 void add(int x,int v,int n)
18 {
19     while(x <= n)
20     {
21         c[x] += v;
22         x += x & -x;
23     }
24 }
25 struct Node{
26     int x,id;
27 };
28 vector<Node> b[N * 2];
29 int a[N];
30 int ans[N];
31 int main()
32 {
33     scanf("%d", &t);
34     while(t -- )
35     {
36         int n;
37         scanf("%d", &n);
38         for(int i = 1; i <= 2 * n;i ++) c[i] = 0,b[i].clear();
39         for(int i = 1; i <= n; i ++){ //对右端点进行排序 
40             scanf("%d", &a[i]);
41             if(i <= a[i]){ //b数组的存的右端点的值是唯一的
42                 b[a[i]].push_back({i,a[i]}); //右边a[i] 表示询问的编号
43                 b[a[i] + n].push_back({i + n,a[i]});
44             }else {
45                 b[a[i] + n].push_back({i,a[i]}); //i表示左端点，a[i] + n 表示右端点
46             }
47         }
48         for(int q = 1; q <= 2 * n; q ++){
49             for(auto [x, id] : b[q]){
50                 if(x <= n) ans[id] = q - x - (sum(q - 1) - sum(x));
51                 add(x,1,2 * n);
52             }
53         }
54         for(int i = 1; i <= n; i ++) printf("%d ",ans[i]);
55         cout << endl;
56     }
57     return 0;
58 }