B3695 暴力

· · 题解

B3695 暴力

我一开始看这道题目觉得很难，于是着手打了暴力，然后果然就是超时了，但是开了 O_2 以后就 AC ，再这里，蒟蒻讲讲这题我的打法。

这是好久以前的事情了，因为现在数据被加强了。

真实题解

直接建数组存数据是肯定不行的，但我们发现1 \leq \sum_{i = 1}^n c_i \leq 10^6 ，就可以想到用一个 vector 去存储数据。

接下来是操作的问题。我用 l_i 和 r_i 数组表示第 i 个集合的最左端和最右端。 now_i 表示第 i 个集合现在与原来相比需要加上的值。

我们来分类分析。

加和减是类似的，在这里我分析加法。

我们就把 now_x 加上 y 之后看看是否需要更新 l 数组和 r 数组。

if(o==1){
    now[x]+=y;
    while(l[x]<=r[x]&&a[x][r[x]]+now[x]>m) r[x]--;
}

减法同理，大家先思考，不会的看下面。

我处理出交集，然后并集 = 两个集合个数总和 - 交集个数，对称差 = 两个集合并集个数 - 交集个数。

交集个数我们可以用尺取法用比较快的速度查找。

jiao=0;
now1=l[x],now2=l[y];
while(now1<=r[x]&&now2<=r[y]){
    if(a[x][now1]+now[x]==a[y][now2]+now[y]) jiao++,now1++,now2++;
    else if(a[x][now1]+now[x]>a[y][now2]+now[y]) now2++;
    else if(a[x][now1]+now[x]<a[y][now2]+now[y]) now1++;
}
if(o==3) ans=jiao ;
if(o==4) ans=r[x]+r[y]-l[x]-l[y]+2-jiao;
if(o==5) ans=r[x]+r[y]-l[x]-l[y]+2-jiao*2;
put(ans);//put函数是输优

然后就很容易写出完整代码了。

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+5;
int n,m,l[N],r[N],now[N],o,x,y,q,minn[N],maxn[N],now1,now2,jiao,ans;
vector<int>a[N];
inline void read(int &res){
    res=0;int f=1;char ch=getchar();
    while('0'>ch||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while('0'<=ch&&ch<='9'){
        res=(res<<1)+(res<<3)+(ch^48);
        ch=getchar();
    }
    res*=f;
}
inline void put(int x){
    if(x<0) putchar('-'),x=-x;
    int i=1;
    while(i*10<=x) i*=10;
    while(i){
        putchar(x/i+'0');
        x%=i;i/=10;
    }
}
int main(){
    read(n),read(m),read(q);
    for(int i=1;i<=n;i++){
        l[i]=1;
        read(r[i]);a[i].push_back(0);
        for(int j=1;j<=r[i];j++){
            read(x);
            a[i].push_back(x);//vector读入
        }
    }
    while(q--){
        read(o),read(x),read(y);
        if(o==1){
            now[x]+=y;
            while(l[x]<=r[x]&&a[x][r[x]]+now[x]>m) r[x]--;
        }
        else if(o==2){
            now[x]-=y;
            while(l[x]<=r[x]&&a[x][l[x]]+now[x]<1) l[x]++;
        }
        else{
            jiao=0;
            now1=l[x],now2=l[y];
            while(now1<=r[x]&&now2<=r[y]){
                if(a[x][now1]+now[x]==a[y][now2]+now[y]) jiao++,now1++,now2++;
                else if(a[x][now1]+now[x]>a[y][now2]+now[y]) now2++;
                else if(a[x][now1]+now[x]<a[y][now2]+now[y]) now1++;
            }
            if(o==3) ans=jiao ;
            if(o==4) ans=r[x]+r[y]-l[x]-l[y]+2-jiao;
            if(o==5) ans=r[x]+r[y]-l[x]-l[y]+2-jiao*2;
            put(ans);
            putchar('\n');
        }

    }
    return 0;
}