A string

记下 pre，\(\mathcal{O}(n)\) 做完了。

B subset

小思维题。
先考虑如果全是非负数咋做，先给价值排序，定义一个方案 \(p(val,id)\)，表示这种方案考虑到了 \(id\) 位置，价值为 \(val\)，可以由它再扩展两个方案，一种是拿下一个 \(p(val+w[id+1],id+1)\)，一种是舍去当前的，拿下一个 \(p(val-w[id]+w[id+1],id+1)\)，这样算的话总方案数是不重不漏的。
把方案放到小根堆里，每次取堆头为答案，并且用它更新，正确性同最短路。
现在的问题是有负数，可能多拿方案更优，考虑转化问题，\(min\) 表示所有负数绝对值的和，给所有负数取正，然后用上面的方法处理。最后的价值全部减去 \(min\)，此时如果选到了一个正数，就表示这种方案选择了这个正数，如果选择了一个负数，则表示没有选这个负数，因为最后的价值都要减去 \(min\)，选择了后贡献就抵消了。

C rook

对于查询矩阵，设有车的行数为 \(hang\)，有车的列数为 \(lie\)，宽度为 \(w\)，高度为 \(h\)，则 \(ans=hang\times w+lie\times h-hang\times lie\)，解决行和列同理，下面只说行的情况。
所以现在问题就变成了子矩阵数颜色问题，考虑转化为序列问题，给所有车按行坐标排个序，每次查询就能知道对应的车的区间，考虑莫队，加入一个车是 \(\mathcal{O}(1)\) 的，查询考虑拿值域分块维护列坐标，每次 \(\mathcal{O}(\sqrt n)\)，总体时间复杂度为 \(\mathcal{O}(q\sqrt k)\)，瓶颈在于莫队。
别的做法找时间细说。

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2e5+10;
int n,m,k,Q,l=1,r=0,len,mp[N],lenk,id[N],idk[N],s[N],ans[N];
struct node{
    int x,y;
    friend bool operator<(node a,int b){return a.x<b;};
    friend bool operator<(int b,node a){return b<a.x;};
}a[N];
struct QU{
    int L,R,num,c1,r1,c2,r2;
    bool operator<(const QU&a)const{
        return id[L]==id[a.L]?((id[L]&1)?R<a.R:R>a.R):id[L]<id[a.L];
    }
}q[N];
inline void move(int p,int val){
    int y=a[p].y,kid=idk[y];
    mp[y]+=val;if(mp[y]-val==0&&mp[y]==1)s[kid]++;if(mp[y]-val==1&&mp[y]==0)s[kid]--;
}
inline int query(int l,int r){
    int lid=idk[l],rid=idk[r],res=0;
    if(rid-lid<=1){
        for(int i=l;i<=r;++i)mp[i]&&res++;
        return res;
    }
    for(int i=lid+1;i<=rid-1;++i)res+=s[i];
    for(int i=l;idk[i]==lid;++i)mp[i]&&res++;
    for(int i=r;idk[i]==rid;--i)mp[i]&&res++;
    return res;
}
inline void sol(int pd){
    std::sort(a+1,a+k+1,[](node &a,node &b){return a.x<b.x;});
    for(int i=1;i<=Q;++i){
        int c1=q[i].c1,r1=q[i].r1,c2=q[i].c2,r2=q[i].r2;
        q[i]={std::lower_bound(a+1,a+k+1,c1)-a,std::upper_bound(a+1,a+k+1,c2)-a-1,q[i].num,c1,r1,c2,r2};
    }
    std::sort(q+1,q+Q+1);
    for(int i=1;i<=Q;++i){
        int L=q[i].L,R=q[i].R;
        if(L>R)continue;
        while(l<L)move(l++,-1);
        while(r<R)move(++r,1);
        while(l>L)move(--l,1);
        while(r>R)move(r--,-1);
        int res=query(q[i].r1,q[i].r2);
        if(!pd)ans[q[i].num]=res;
        else{
            int w=q[i].c2-q[i].c1+1,h=q[i].r2-q[i].r1+1,hang=res,lie=ans[q[i].num];
            ans[q[i].num]=hang*w+lie*h-hang*lie;
        }
    }
}
signed main(){
    freopen("rook.in","r",stdin);freopen("rook.out","w",stdout);
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    n=read(),m=read(),k=read(),Q=read();len=std::sqrt(k);
    int mx=std::max(n,m);lenk=std::sqrt(mx);
    for(int i=1;i<=mx;++i)idk[i]=(i-1)/lenk+1;
    for(int i=1;i<=k;++i){
        id[i]=(i-1)/len+1;
        a[i].x=read(),a[i].y=read();
    }
    for(int i=1;i<=Q;++i){q[i].c1=read(),q[i].r1=read(),q[i].c2=read(),q[i].r2=read(),q[i].num=i;}
    sol(0);
    l=1,r=0;
    std::fill(mp+1,mp+mx+1,0);std::fill(s+1,s+lenk+2,0);
    for(int i=1;i<=k;++i)std::swap(a[i].x,a[i].y);for(int i=1;i<=Q;++i)std::swap(q[i].c1,q[i].r1),std::swap(q[i].c2,q[i].r2);
    sol(1);
    for(int i=1;i<=Q;++i)std::cout<<ans[i]<<'\n';
}