【LOJ2254】【SNOI2017】一个简单的询问

莫队算法即可。

本题粗看似乎无从下手,考虑将一个询问拆成多个前缀询问。

f(x,y)=ans(1,x,1,y)f(x,y)=ans(1,x,1,y),g(x,y)=get(1,x,y)g(x,y)=get(1,x,y),我们有

ans(l1,r1,l2,r2)=x=0(g(r1,x)g(l11,x))×(g(r2,x)g(l21,x))=x=0g(r1,x)×g(r2,x)g(r1,x)×g(l21,x)g(l11,x)×g(r2,x)+g(l11,x)×g(l21,x)=f(r1,r2)f(r1,l21)f(l11,r2)+f(l11,l21) \begin{aligned} ans(l1,r1,l2,r2) & =\sum_{x=0}^{\infty}(g(r1,x)-g(l1-1,x))\times (g(r2,x)-g(l2-1,x))\\ & =\sum_{x=0}^{\infty}g(r1,x)\times g(r2,x)-g(r1,x)\times g(l2-1,x)\\ & -g(l1-1,x)\times g(r2,x)+g(l1-1,x)\times g(l2-1,x)\\ & =f(r1,r2)-f(r1,l2-1)-f(l1-1,r2)+f(l1-1,l2-1) \end{aligned}

于是用莫队计算ff即可。

用两个数组分别维护两个前缀中每个数的出现次数,增删数时可以O(1)O(1)更新答案。

时间复杂度O(nn)O(n \sqrt n)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("2254.txt","r",stdin);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
ll ans[50001],now;
int a[50001],cnt[2][50001],pl[50001];
struct query{
    int p,sgn,l1,l2;
    bool operator <(const query& rhs)const{
        return pl[l1]!=pl[rhs.l1]?pl[l1]<pl[rhs.l1]:l2<rhs.l2;
    }
}q[200001];
void update(int p,int v,int sgn){
    now+=sgn*cnt[p^1][v];
    cnt[p][v]+=sgn;
}
int main(){
    init();
    int n=readint(),cur=0;
    for(int i=1;i<=n;i++)
        a[i]=readint();
    int m=readint();
    for(int i=1;i<=m;i++){
        int l1=readint()-1,r1=readint(),l2=readint()-1,r2=readint();
        if (l1)
            q[++cur]=(query){i,-1,l1,r2};
        if (l2)
            q[++cur]=(query){i,-1,l2,r1};
        if (l1 && l2)
            q[++cur]=(query){i,1,l1,l2};
        q[++cur]=(query){i,1,r1,r2};
    }
    int sz=sqrt(n)+0.5;
    for(int i=1;i<=n;i++)
        pl[i]=(i-1)/sz+1;
    sort(q+1,q+cur+1);
    int l1=0,l2=0;
    for(int i=1;i<=cur;i++){
        while(l1<q[i].l1)
            update(0,a[++l1],1);
        while(l1>q[i].l1)
            update(0,a[l1--],-1);
        while(l2<q[i].l2)
            update(1,a[++l2],1);
        while(l2>q[i].l2)
            update(1,a[l2--],-1);
        ans[q[i].p]+=now*q[i].sgn;
    }
    for(int i=1;i<=m;i++)
        printf("%lld\n",ans[i]);
}

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

本文链接:https://q234rty.top/2017/08/02/loj2254/