牛客练习赛73D 离别（线段树）

经典套路，离线枚举右端点计算左端点。感觉这种题都已经出烂了

首先我们观察到，对于一个右端点i来说，合法的一定是一段区间，也就是最大值是k-k+1的区间，因此我们对每个种类维护一个队列

这样可以计算到达k和k+1的信息，并维护合法区间。

之后就是线段树插入和查询了，插入就是对于我们枚举的右端点，去插入她合法的左区间，也就是以他为右端点合法的区间个数

这样查询的时候因为我们是从小到大离线询问的，因此现在线段树里的信息的都是右端点在当前计算点的左边，因此只要查询合法的左端点的个数即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
typedef pair<int,int> plll;
const int N=3e5+10;
const int inf=0x3f3f3f3f;
const int mod=998244353;
struct node{
    int l,r;
    ll sum;
    int lazy;
}tr[N<<2];
int n,q1,k;
queue<int> q[N];
int f[N],e[N];
int a[N];
struct Q{
    int l,id;
}s[N];
vector<Q> num[N];
ll ans[N];
void build(int u,int l,int r){
    if(l==r){
        tr[u]={l,r,0,0};
    }
    else{
        tr[u]={l,r};
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
    }
}
void pushup(int u){
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u){
    int x=tr[u].lazy;
    tr[u<<1].sum+=(tr[u<<1].r-tr[u<<1].l+1)*x,tr[u<<1|1].sum+=(tr[u<<1|1].r-tr[u<<1|1].l+1)*x;
    tr[u<<1].lazy+=x,tr[u<<1|1].lazy+=x;
    tr[u].lazy=0;
}
void modify(int u,int l,int r,int x){
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].sum+=(tr[u].r-tr[u].l+1)*x;
        tr[u].lazy+=x;
        return ;
    }
    if(tr[u].lazy)
        pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)
        modify(u<<1,l,r,x);
    if(r>mid)
        modify(u<<1|1,l,r,x);
    pushup(u);
}
ll query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r){
        return tr[u].sum;
    }
    if(tr[u].lazy)
        pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    ll ans=0;
    if(l<=mid)
        ans+=query(u<<1,l,r);
    if(r>mid)
        ans+=query(u<<1|1,l,r);
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>q1>>k;
    int i;
    for(i=1;i<=n;i++){
        cin>>a[i];
    }
    int flag=0,sign=0;
    build(1,1,n);
    for(i=1;i<=n;i++){
        q[a[i]].push(i);
        if(q[a[i]].size()==k+1){
            flag=max(flag,q[a[i]].front());
            q[a[i]].pop();
        }
        if(q[a[i]].size()==k){
            sign=max(sign,q[a[i]].front());
        }
        if(sign>0){
            f[i]=flag+1;
            e[i]=sign;
        }

    }
    for(i=1;i<=q1;i++){
        int l,r;
        cin>>l>>r;
        num[r].push_back({l,i});
    }
    for(i=1;i<=n;i++){
        if(e[i])
            modify(1,f[i],e[i],1);
        for(auto t:num[i]){
           ans[t.id]=query(1,t.l,i);
        }
    }
    for(i=1;i<=q1;i++){
        cout<<ans[i]<<endl;
    }
}