闲话

巨佬

思路

这题一看就是贪心，购买时间越晚的物品越早卖，否则时间晚买的物品可以把时间早买的给换掉，并对左端点更靠右的物品有贡献

那么对每种类型的物品开一个栈，栈内为还未卖出的物品节点，每次遇到一个可以卖出的节点就弹栈。设栈顶元素为 $L$，卖出节点为 $R$，则询问 $[l_i,r_i]$ 的答案为满足 $[L,R] \subseteq [li,ri]$ 的二元组 $(L,R)$ 的个数。

时间复杂度: $O(\log n)$。

代码

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}
int stk[10],tp;
inline void write(int x)
{
    if(!x) return puts("0"),void();
    tp=0;
    while(x) stk[++tp]=x%10,x/=10;
    while(tp) putchar(stk[tp--]^48);
    putchar('\n');
}
const int N=5e5+10;
struct ok{
    int l,id;
};
int n,q,a[N],c[N],Tr[N],ans[N];
vector<int>Q[N];
vector<ok>ask[N];
void add(int x) {for(;x;x-=(x&-x)) ++Tr[x];}
int query(int x,int res=0) {for(;x<=n;x+=(x&-x)) res+=Tr[x];return res;}
int main()
{
    n=read(),q=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1,x;i<=n;i++)
    {
        x=read();
        if(a[i]&&!Q[x].empty()) c[i]=Q[x].back(),Q[x].pop_back();
        if(!a[i]) Q[x].push_back(i);
    }
    for(int i=1,l,r;i<=q;i++)
        l=read(),r=read(),ask[r].push_back((ok){l,i});
    for(int i=1;i<=n;i++)
    {
        add(c[i]);
        for(ok x:ask[i]) ans[x.id]=query(x.l);
    }
    for(int i=1;i<=q;i++) write(ans[i]);
    return n&0;
}