P1972

Aryper · 2021-08-11 17:55:32 · 个人记录

[SDOI2009]HH的项链

我们采用离线，先按照右端点从小到大排序。

然后每次求取下一个区间的答案的时候从 r_{i-1}+1 到 r_i 进行更新。

具体的更新用树状数组维护（[1,x] 中有多少颜色最后一次出现）。

我们可以记一个数组 last_i 表示颜色 i 最后一次出现的位置（对于更新到的位置）。

然后比如说在更新的时候，col_j 是第一次出现，那么我们可以将 last_{col_j} 赋为 j，然后更新 [1,j] 的信息即可。

如果说 col_j 曾经出现过，我们不仅要更改 last 的值，修改 [1,j] 的信息，还需要再修改 [1,last_{col_j}] 的信息。

这样子求答案就直接用 c_r-c_{l-1} 即可。

时间复杂度 O((n+m)\log n)。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=1e6;

struct node{
    ll l,r,id,ans;
}a[N+5];

ll n,m;

ll lst[N+5],col[N+5],c[N+5];

void add(ll x,ll y) {
    for(;x<=n;x+=x&-x) c[x]+=y;
}

ll ask(ll x) {
    ll res=0;
    for(;x;x-=x&-x) res+=c[x];
    return res;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

bool cmp(node x,node y) {
    if(x.r==y.r) return x.l<y.l;
    return x.r<y.r;
}

bool cmp_(node x,node y) {
    return x.id<y.id;
}

int main() {

    n=read();

    for(ll i=1;i<=n;i++) {
        col[i]=read();
    }

    m=read();

    for(ll i=1;i<=m;i++) {
        a[i].l=read();a[i].r=read();a[i].id=i;
    }

    sort(a+1,a+m+1,cmp);

    for(ll i=1;i<=m;i++) {
        for(ll j=a[i-1].r+1;j<=a[i].r;j++) {
            if(lst[col[j]]) add(lst[col[j]],-1);
            add(j,1);lst[col[j]]=j;
        }
        a[i].ans=ask(a[i].r)-ask(a[i].l-1);
    }

    sort(a+1,a+m+1,cmp_);

    for(ll i=1;i<=m;i++) {
        write(a[i].ans);putchar('\n');
    }

    return 0;
}