水晶-题解

Hope2075 · 2019-08-14 18:01:23 · 题解

出题人突然想卡掉O(n\log n)的做法，于是加强了最后一个点的数据范围（1\times 10^6 改为2.5\times 10^6），然后优化了一下交互库和std，但时限没改

结果就是有点卡常（不过我的std好像优化得不很好）

最后一个点std用时2.4秒（好像和之前一样QWQ），O(n\log n)的算法约3.2秒

（借用的小粉兔的代码）

实在也没啥好办法了QWQ

题解除了代码，别的都没变

如果管理员认为不合适，请私信，我可以把数据改回去

题意：给出两个长为n的序列(a_i,na_i),(b_i,nb_i)

你需要求：

1.\sum_{i=1}^n\sum_{j=1}^n na_i\cdot nb_j \cdot [b_j>a_i]

也就是所有满足b_j>a_i的na_i\cdot nb_j之和

2.给出x,y,z,w，如果序列(a_i,na_i)只保留满足a_i大小在a_x和a_y之间的部分，序列(b_i,nb_i)只保留满足b_i大小在b_z和b_w之间的部分，那么第一问的答案

算法1

暴力枚举i,j

时间复杂度O(n^2q)

期望得分4分

算法2

先对两个序列分别按照a_i,b_i从小到大排序

这时候发现，如果对于一个b_i，某个a_j能产生贡献(j>1)，那么a_{j-1}也能产生贡献

而当i变大时，最大的能产生贡献的a_j的位置不会向左移动

所以，用双指针求值

从左向右枚举i的位置，并记录满足条件的a_j对应na_j的和，每次移动i后，再移动j，把扫过的部分加上，随后更新答案，加上这个i产生的贡献

对于之后的询问，发现对应a_i和b_i在一段连续的区间里，用类似的方法就能求出答案

为了方便，处理询问前，根据a_x和a_y的大小关系交换x,y，根据b_z和b_w的大小关系交换z,w

关于如何找询问在排序后序列中的位置：这部分完全可以暴力找位置，不影响复杂度

后面的部分可以把序列排序前的值记录下来，根据值进行二分

还有另外一种方法可以O(1)找位置，在最后面讲

时间复杂度O(nq)

期望得分18分

算法3

针对#3

发现a_i,b_i都很小

所以，统计每个a_i,b_i对应na_i,nb_i的和

处理询问时有多种方法，其中一种是：与算法2类似，在对应区间内用双指针法处理

另一个方法在算法5中讲解

暴力找位置再求值即可

时间复杂度O(n+q\cdot a_i)

期望得分11分，结合算法2期望得分29分

算法4

针对#4

发现q很大，n很小

说明询问的总情况数很小

所以枚举所有询问，然后分别求出答案，在询问时就能做到O(1)

时间复杂度O(n^6+q)或O(n^5+q)

期望得分10分，结合算法2期望得分28分

算法5

针对#5

这时候发现n变大了

需要发现一个性质才能继续优化

以样例2为例

把图画出来，其中黄色格子代表可以产生贡献

考虑询问2 2 2 2

答案很明显是6

这样就能看出，实际是一个前缀和

所以，按照图中的做法弄一个二维数组，然后求二维前缀和

处理询问时，找到位置后，差分一下，就能O(1)求出答案（找位置可能是O(\log n)）

空间大概100MB，能开得下

也可以用类似的思路过#3：把连续的一段压成一个点，然后就能用类似的思路做了，时间复杂度是O(a_i^2+q)

时间复杂度O(n^2+q\log n)或O(n^2+q)

期望得分36分，结合其它算法能得到更高的分数

算法6

对于最后两组数据，n太大了，不能直接用前缀和

这时候，使用一种类似的思路

如果n很大，那么按照上面画出来的图可能是这样的

那么，求前缀和需要的部分可能有这两种情况

（恰好在边界归为任何一种都可以）

第一种情况：a_i\ge b_j

这时候，需要求的可以转化为所有满足k\le j的b_k产生的贡献

这部分可以用算法2的思路求，不同之处是记录每个b_j的值

第二种情况：a_i<b_j

这时候可以看成一个矩形减去一块

矩形部分很容易计算，用na_i和nb+j的前缀和就能算出来

而减去的一块看起来很像上面一种情况

不同之处是，这部分是a_k的值，而且是不能产生贡献的部分

这样就和上面类似了

当然，还有另外3种思路，不过基本是类似的，只是求前缀和的方向不同

时间复杂度O(n+q\log n)或O(n+q)

虽然std的内存使用约160MB，但还是请注意内存使用情况，有些写法可能就会消耗更多的空间

期望得分100分

关于O(1)找位置

在排序的时候，先记录每个数原来的位置

排完序后，把数字相同的部分合并，然后根据原位置的信息把位置映射到新的位置

这样，就可以O(1)找到位置了

注意：排序要用基数排序，否则复杂度会带log

~~其实出题人本来想卡带\log的算法的，但是出题人的std常数有点大，不太好卡，于是就放过去了~~

上面一行作废，现在O(n\log n)算法不容易卡过去

代码：

#include<cstdio>
using namespace std;
#define u32 unsigned int
#define u64 unsigned long long
int cl;
const int N=2500007;
const long long M=998244353LL;
int n,q,k;
int a[N],na[N],b[N],nb[N];
int x,y,z,u;
namespace lib{
    u64 read(){
        u64 n=0;
        char c=getchar();
        while(c<'0'||c>'9')c=getchar();
        while(c>='0'&&c<='9'){
            n=n*10+c-'0';
            c=getchar();
        }
        return n;
    }
    char r[30];
    void write(u64 num){
        if(num==0){
            putchar('0');
            return;
        }
        int t=0;
        while(num){
            r[t++]=num%10+'0';
            num/=10;
        }
        while(t)putchar(r[--t]);
    }
    u64 s;
    u64 rand(u64 l,u64 r){
        s=s*19260817+1;
        return ((s>>8)%(r-l+1)+l);
    }
    int ra,t;
    void init(){
        n=read();k=read();
        if(k<2){
            for(int i=1;i<=n;i++){
                a[i]=read();na[i]=read();
            }
            for(int i=1;i<=n;i++){
                b[i]=read();nb[i]=read();
            }
        }else{
            s=read();ra=read();
            u64 bacs=s;
            for(int i=1;i<=n;i++){
                s=s*19260817+1;
                a[i]=((s>>8)%ra+1);
                //a[i]=rand(1,ra);
                s=s*19260817+1;
                //na[i]=((s>>8)%(M-1)+1);
                //na[i]=rand(1,M-1);
            }
            s=bacs;
            for(int i=1;i<=n;i++){
                s=s*19260817+1;
                //a[i]=((s>>8)%ra+1);
                //a[i]=rand(1,ra);
                s=s*19260817+1;
                na[i]=((s>>8)%(M-1)+1);
                //na[i]=rand(1,M-1);
            }
            bacs=s;
            for(int i=1;i<=n;i++){
                s=s*19260817+1;
                b[i]=((s>>8)%ra+1);
                //a[i]=rand(1,ra);
                s=s*19260817+1;
                //nb[i]=((s>>8)%(M-1)+1);
            }
            s=bacs;
            for(int i=1;i<=n;i++){
                s=s*19260817+1;
                //b[i]=((s>>8)%ra+1);
                //a[i]=rand(1,ra);
                s=s*19260817+1;
                nb[i]=((s>>8)%(M-1)+1);
            }
        }
        q=read();
    }
    u64 lastans;
    u64 res;
    void reply(u64 num){
        if(k<2){
            write(num);putchar('\n');
        }else{
            res=res*233+num;
        }
        lastans^=num;
    }
    void query(){
        if(k<2){
            x=read();y=read();z=read();u=read();
        }else{
            s=s*19260817+1;
            x=((s>>8)%n+1);
            s=s*19260817+1;
            y=((s>>8)%n+1);
            s=s*19260817+1;
            z=((s>>8)%n+1);
            s=s*19260817+1;
            u=((s>>8)%n+1);
            //x=rand(1,n);y=rand(1,n);z=rand(1,n);u=rand(1,n);
        }
        if(k&1){
            int t=lastans%n+1;
            if((x+=t)>n)x-=n;
            if((y+=t)>n)y-=n;
            if((z+=t)>n)z-=n;
            if((u+=t)>n)u-=n;
            /*x=(x+lastans)%n+1;
            y=(y+lastans)%n+1;
            z=(z+lastans)%n+1;
            u=(u+lastans)%n+1;*/
        }
    }
    void stop(){
        if(k>=2){write(res);putchar('\n');}
    }
}
long long ans;
int aid[N],bid[N];
int swp[N],sid[N],cnt[65536];
void sort(){
    //这里把base改成了256，不过好像区别不大
    cnt[0]=1;
    for(int i=1;i<256;i++)cnt[i]=0;
    for(int i=1;i<=n;i++)++cnt[a[i]&0xff];
    for(int i=1;i<256;i++)cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--){
        swp[--cnt[a[i]&0xff]]=a[i];
        sid[cnt[a[i]&0xff]]=i;
    }

    cnt[0]=1;
    for(int i=1;i<256;i++)cnt[i]=0;
    for(int i=1;i<=n;i++)++cnt[(swp[i]>>8)&0xff];
    for(int i=1;i<256;i++)cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--){
        a[--cnt[(swp[i]>>8)&0xff]]=swp[i];
        aid[cnt[(swp[i]>>8)&0xff]]=sid[i];
    }

    cnt[0]=1;
    for(int i=1;i<256;i++)cnt[i]=0;
    for(int i=1;i<=n;i++)++cnt[(a[i]>>16)&0xff];
    for(int i=1;i<256;i++)cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--){
        swp[--cnt[(a[i]>>16)&0xff]]=a[i];
        sid[cnt[(a[i]>>16)&0xff]]=aid[i];
    }

    cnt[0]=1;
    for(int i=1;i<256;i++)cnt[i]=0;
    for(int i=1;i<=n;i++)++cnt[(swp[i]>>24)&0xff];
    for(int i=1;i<256;i++)cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--){
        a[--cnt[(swp[i]>>24)&0xff]]=swp[i];
        aid[cnt[(swp[i]>>24)&0xff]]=sid[i];
    }

    cnt[0]=1;
    for(int i=1;i<256;i++)cnt[i]=0;
    for(int i=1;i<=n;i++)++cnt[b[i]&0xff];
    for(int i=1;i<256;i++)cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--){
        swp[--cnt[b[i]&0xff]]=b[i];
        sid[cnt[b[i]&0xff]]=i;
    }

    cnt[0]=1;
    for(int i=1;i<256;i++)cnt[i]=0;
    for(int i=1;i<=n;i++)++cnt[(swp[i]>>8)&0xff];
    for(int i=1;i<256;i++)cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--){
        b[--cnt[(swp[i]>>8)&0xff]]=swp[i];
        bid[cnt[(swp[i]>>8)&0xff]]=sid[i];
    }

    cnt[0]=1;
    for(int i=1;i<256;i++)cnt[i]=0;
    for(int i=1;i<=n;i++)++cnt[(b[i]>>16)&0xff];
    for(int i=1;i<256;i++)cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--){
        swp[--cnt[(b[i]>>16)&0xff]]=b[i];
        sid[cnt[(b[i]>>16)&0xff]]=bid[i];
    }

    cnt[0]=1;
    for(int i=1;i<256;i++)cnt[i]=0;
    for(int i=1;i<=n;i++)++cnt[(swp[i]>>24)&0xff];
    for(int i=1;i<256;i++)cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--){
        b[--cnt[(swp[i]>>24)&0xff]]=swp[i];
        bid[cnt[(swp[i]>>24)&0xff]]=sid[i];
    }

}
long long sum;
int cuta[N],cutb[N];
int prea[N],preb[N];
int pa[N],pb[N];
inline long long sol(int i,int j){
    if(a[i]>=b[j]){
        return cutb[j];
    }else{
        return ((cuta[i]-1LL*prea[i]*(preb[n]-preb[j]))%M+M)%M;
    }
}
int main(){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    lib::init();

    sort();
    for(int i=1;i<=n;i++){
        swp[i]=na[aid[i]];
    }
    for(int i=1;i<=n;i++){
        na[i]=swp[i];
    }
    sid[aid[1]]=1;
    for(int i=2;i<=n;i++){
        if(a[i]==a[i-1]){
            sid[aid[i]]=sid[aid[i-1]];
        }else{
            sid[aid[i]]=i;
        }
    }
    for(int i=1;i<=n;i++){
        aid[i]=sid[i];
    }
    for(int i=n-1;i>=1;i--){
        if(a[i]==a[i+1]){
            na[i]+=na[i+1];
            na[i]%=M;
            na[i+1]=0;
        }
    }
    for(int i=1;i<=n;i++)prea[i]=(prea[i-1]+na[i])%M;

    for(int i=1;i<=n;i++){
        swp[i]=nb[bid[i]];
    }
    for(int i=1;i<=n;i++){
        nb[i]=swp[i];
    }
    sid[bid[1]]=1;
    for(int i=2;i<=n;i++){
        if(b[i]==b[i-1]){
            sid[bid[i]]=sid[bid[i-1]];
        }else{
            sid[bid[i]]=i;
        }
    }
    for(int i=1;i<=n;i++){
        bid[i]=sid[i];
    }
    for(int i=n-1;i>=1;i--){
        if(b[i]==b[i+1]){
            nb[i]+=nb[i+1];
            nb[i]%=M;
            nb[i+1]=0;
        }
    }
    for(int i=1;i<=n;i++)preb[i]=(preb[i-1]+nb[i])%M;

    sum=0;
    for(int i=1;i<=n;i++){
        sum+=nb[i];
        sum%=M;
    }
    int j=1;
    for(int i=1;i<=n;i++){
        while(j<=n&&a[i]>=b[j]){
            sum-=nb[j];
            sum%=M;
            sum+=M;
            sum%=M;
            j++;
        }
        ans+=1LL*sum*na[i];
        ans%=M;
        pa[i]=j;
        cuta[i]=ans;
    }

    sum=0;
    ans=0;
    j=1;
    for(int i=1;i<=n;i++){
        while(j<=n&&b[i]>a[j]){
            sum+=na[j];
            sum%=M;
            j++;
        }
        ans+=1LL*sum*nb[i];
        ans%=M;
        pb[i]=j;
        cutb[i]=ans;
    }

    lib::reply(ans);

    for(int i=1;i<=q;i++){
        lib::query();

        x=aid[x];y=aid[y];
        if(a[x]>a[y]){u32 t=x;x=y;y=t;}
        z=bid[z];u=bid[u];
        if(b[z]>b[u]){u32 t=z;z=u;u=t;}
        x--;z--;

        ans=0;
        ans+=sol(y,u);
        ans-=sol(x,u);
        ans-=sol(y,z);
        ans+=sol(x,z);
        ans=(ans%M+M)%M;

        lib::reply(ans);
    }
    lib::stop();
}

~~这题别忘了IO模板的100多行~~