P1972-[SDOI2009]HH的项链

客官°小女子只卖身不卖艺 2023-06-01 08:57 46阅读 0赞

1 #include <bits/stdc++.h>
     2 typedef long long ll;
     3 using namespace std;
     4 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     5 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     6 #define INF 0x3f3f3f3f
     7 #define MOD 1000000007
     8 #define pb push_back
     9 #define maxn 100003
    10 inline ll read()
    11 {
    12     ll ans = 0;
    13     char ch = getchar(), last = ' ';
    14     while(!isdigit(ch)) last = ch, ch = getchar();
    15     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    16     if(last == '-') ans = -ans;
    17     return ans;
    18 }
    19 inline void write(ll x)
    20 {
    21     if(x < 0) x = -x, putchar('-');
    22     if(x >= 10) write(x / 10);
    23     putchar(x % 10 + '0');
    24 }
    25 
    26 struct q
    27 {
    28     int l;
    29     int r;
    30     int id;
    31     bool operator < (q b)
    32     {
    33         return r < b.r;
    34     }
    35 };
    36 int c[1000003];
    37 int N,R;
    38 int ask(int x)
    39 {
    40     int ans = 0;
    41     for(; x; x -= x&-x) ans += c[x];
    42     return ans;
    43 }
    44 void add(int x,int y)
    45 {
    46     for(; x <= N; x += x & -x) c[x]+=y;
    47 }
    48 
    49 q Q[1000003];
    50 int num[1000003];
    51 int ans[1000003];
    52 int H[1000003];
    53 int pre[1000003];
    54 int main()
    55 {
    56     N = read();
    57     _for(i,1,N+1)
    58     num[i] = read();
    59     R = read();
    60     _for(i,1,R+1)
    61     {
    62         Q[i].l = read();
    63         Q[i].r = read();
    64         Q[i].id = i;
    65     }
    66     sort(Q+1,Q+R+1);
    67     int j = 1;
    68     _for(i,1,R+1)
    69     {
    70         while(j<=Q[i].r)
    71         {
    72             if(!H[num[j]])
    73             {
    74                 H[num[j]] = 1;
    75                 pre[num[j]] = j;
    76             }
    77             else
    78             {
    79                 add(pre[num[j]],-1);
    80                 pre[num[j]] = j;
    81             }
    82             add(j,1);
    83             j ++;
    84         }
    85         ans[Q[i].id] = ask(Q[i].r)-ask(Q[i].l-1);
    86     }
    87     _for(i,1,R+1)
    88         printf("%d\n",ans[i]);
    89     return 0;
    90 }

转载于:https://www.cnblogs.com/Asurudo/p/11572498.html