题解

对每种类型的物品可以独立考虑：序列中出现该颜色的点按顺序组成一串 “+1（买）/ -1（卖）”。从空库存出发顺扫，能成交的次数等于匹配到的卖点个数。对一段子序列，其成交次数由三项信息唯一决定：

• sum：净变化（买减卖）。
• minPref：从 0 开始的前缀最小值。
• sells：卖点数量。

若从空库存进入这段子序列，则未能匹配的卖点数为 max(0, -minPref)，故成交数为 sells - max(0, -minPref)。

上述三元组可作为区间的“状态”，且满足可结合的合并公式（类似括号序列）：

sum = sumA + sumB
minPref = min(minPrefA, sumA + minPrefB)
sells = sellsA + sellsB

因此，一段颜色串的状态可在 O(1) 内合并。

用 Mo 算法维护区间

询问是区间子序列，天然适合使用 Mo 算法（按块排序、移动左右端点）。移动端点仅在区间两端插入/删除一个元素，不会打乱内部顺序。

对每种颜色维护当前区间内它的事件序列，以及对应的状态三元组。需要支持：

• 从左端插入/删除一个事件；
• 从右端插入/删除一个事件；
• O(1) 查询该颜色的成交数。

为保持顺序并兼顾双端操作，对每个颜色使用两个栈模拟队列：左栈表示区间前部（栈顶即最左端），右栈表示后部（栈顶即最右端）。每个栈同时维护一串前缀状态，便于 O(1) 获得整栈状态。弹空时将另一栈整体搬运过来，代价均摊仍为 O(1)。

区间内该颜色的总状态即 combine(leftState, rightState)。由此即可得到成交数并用全局答案维护差分更新。

总修改次数约为 O((n+q)√n)，每次常数操作，能满足时限。

复杂度

• 时间：O((n+q) * sqrt(n))。
• 空间：存储每个颜色的两个栈及状态，总元素数不超过当前区间长度，整体 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

struct Node{
    int sum;   // +1/-1 总和
    int minp;  // 前缀最小值（含空前缀 0）
    int sells; // 卖点数量
};

Node combine(const Node& a,const Node& b){
    return {a.sum + b.sum, min(a.minp, a.sum + b.minp), a.sells + b.sells};
}

struct ColorState{
    vector<int> Lval, Rval;
    vector<Node> Lsum, Rsum; // 前缀状态栈
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    if(!(cin>>n>>q)) return 0;
    vector<int> a(n+1), c(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>c[i];
    struct Query{int l,r,id;};
    vector<Query> qs(q);
    for(int i=0;i<q;i++){
        cin>>qs[i].l>>qs[i].r;
        qs[i].id=i;
    }
    int block=max(1,(int)sqrt(n));
    sort(qs.begin(), qs.end(), [&](const Query& x,const Query& y){
        int bx=x.l/block, by=y.l/block;
        if(bx!=by) return bx<by;
        return (bx&1)? x.r>y.r : x.r<y.r;
    });

    int maxColor=*max_element(c.begin()+1, c.end());
    vector<ColorState> st(maxColor+1);

    auto single=[&](int delta)->Node{
        return Node{delta, min(0, delta), delta==-1};
    };
    auto getSummary=[&](int col)->Node{
        const auto& S=st[col];
        if(S.Lsum.empty() && S.Rsum.empty()) return {0,0,0};
        if(S.Lsum.empty()) return S.Rsum.back();
        if(S.Rsum.empty()) return S.Lsum.back();
        return combine(S.Lsum.back(), S.Rsum.back());
    };
    auto getMatched=[&](int col)->int{
        Node s=getSummary(col);
        int unmatched=max(0, -s.minp);
        return s.sells - unmatched;
    };
    auto pushLeft=[&](int col,int delta){
        auto &S=st[col];
        Node cur=single(delta);
        if(!S.Lsum.empty()) cur=combine(cur, S.Lsum.back());
        S.Lval.push_back(delta);
        S.Lsum.push_back(cur);
    };
    auto pushRight=[&](int col,int delta){
        auto &S=st[col];
        Node cur=single(delta);
        if(!S.Rsum.empty()) cur=combine(S.Rsum.back(), cur);
        S.Rval.push_back(delta);
        S.Rsum.push_back(cur);
    };
    auto rebuildLeft=[&](int col){
        auto &S=st[col];
        while(!S.Rval.empty()){
            int d=S.Rval.back(); S.Rval.pop_back(); S.Rsum.pop_back();
            pushLeft(col,d);
        }
    };
    auto rebuildRight=[&](int col){
        auto &S=st[col];
        while(!S.Lval.empty()){
            int d=S.Lval.back(); S.Lval.pop_back(); S.Lsum.pop_back();
            pushRight(col,d);
        }
    };
    auto popLeft=[&](int col){
        auto &S=st[col];
        if(S.Lval.empty()){
            if(S.Rval.empty()) return;
            rebuildLeft(col);
        }
        S.Lval.pop_back();
        S.Lsum.pop_back();
    };
    auto popRight=[&](int col){
        auto &S=st[col];
        if(S.Rval.empty()){
            if(S.Lval.empty()) return;
            rebuildRight(col);
        }
        S.Rval.pop_back();
        S.Rsum.pop_back();
    };

    auto addLeft=[&](int pos)->int{
        int col=c[pos], delta=(a[pos]==0)?1:-1;
        int old=getMatched(col);
        pushLeft(col,delta);
        return getMatched(col)-old;
    };
    auto addRight=[&](int pos)->int{
        int col=c[pos], delta=(a[pos]==0)?1:-1;
        int old=getMatched(col);
        pushRight(col,delta);
        return getMatched(col)-old;
    };
    auto remLeft=[&](int pos)->int{
        int col=c[pos];
        int old=getMatched(col);
        popLeft(col);
        return getMatched(col)-old;
    };
    auto remRight=[&](int pos)->int{
        int col=c[pos];
        int old=getMatched(col);
        popRight(col);
        return getMatched(col)-old;
    };

    vector<long long> ans(q);
    int curL=1, curR=0;
    long long total=0;
    for(auto qu: qs){
        while(curL>qu.l) total+=addLeft(--curL);
        while(curR<qu.r) total+=addRight(++curR);
        while(curL<qu.l) total+=remLeft(curL++);
        while(curR>qu.r) total+=remRight(curR--);
        ans[qu.id]=total;
    }
    for(int i=0;i<q;i++) cout<<ans[i]<<"\n";
    return 0;
}