题目

题解

考虑环上问题的一般套路:把圆环拆开再复制一份,每次取一个大小为圆环长度的区间。

例如 (1,2,3,4)的圆环就可以拆开成[1,2,3,4,1,2,3,4]

然后拆开以后,每次枚举一个区间,以左端点为X,计算这个区间的答案。

这样就是一个很优秀的$O(n^2)$算法辣!

初步思考一下......

记录$cnt_i$为$1..i$中1的个数-0的个数。

那么左端点(为X的点)为l时,cnt[x]-cnt[l]就是从l到x(l不算) 1的个数-0的个数。

对于前两问,在这个区间里面cnt[x]-cnt[l]>0并且那个位置是1(1是A 0是B),那么那个A是强的。

对于第三问,在这个区间里面cnt[x]-cnt[l]<0并且那个位置是0(0是A 1是B),那么那个A是强的。

那么我们又得到了一个 很优秀的$O(n^2)$解法辣!

我们可以再记录一下一段区间内每个A点的cnt[x]出现的次数。

然后可以直接查找cnt大于/小于cnt[l]的A点个数。

然后我们就又得到了一个$O(n^2)$解法辣

这个查找我会树状数组优化!$O(n\log n)$但是还是过不了$10^7$的数据。

观察每次查找的cnt[l]相对上一次的差的和是$O(n)$的。

我们考虑如果我们知道 小于/大于X 的点数,需要加入/删除某一点或者将X+1/-1,这几个操作都能$O(1)$。

总复杂度$O(n)$

#include<cstdio>
#include<cstring>
#define debug(...) fprintf(stderr,__VA_ARGS__)
int p[40000009];
int seed, n, k, S;
int getrand()
{
    seed = ((seed * 12321) ^ 9999) % 32768;
    return seed;
}
void generateData()
{
    scanf("%d%d%d",&k,&seed,&S);
    int t = 0;
    n = k * 2 + 1;
    memset(p, 0, sizeof(p));
    for (int i = 1; i <= n; i++)
    {
        p[i] = (getrand() / 128) % 2;
        t += p[i];
    }
    int i = 1;
    while (t > k)
    {
        while (p[i] == 0)
            i++;
        p[i] = 0;
        t--;
    }
    while (t < k)
    {
        while (p[i] == 1)
            i++;
        p[i] = 1;
        t++;
    }
    for(int i=1;i<=n;++i)p[i+n]=p[i];
}
int cnt[40000009],f[20000005],line,ans;
int fi[20000005],ians;
void add(int a,int b){
    f[a]+=b;
    if(a>line)ans+=b;
}
void iadd(int a,int b){
    fi[a]+=b;
    if(a<line)ians+=b;
}
int count(int a){
    while(line<a){
        ians+=fi[line];
        ans-=f[++line];
    }
    while(a<line){
        ans+=f[line];
        ians-=fi[--line];
    }
    return ans;
}

int icount(int a){
    while(line<a){

        ians+=fi[line];
        ans-=f[++line];
    }
    while(a<line){
        ans+=f[line];
        ians-=fi[--line];
    }
    return ians;
}
int main()
{
#ifdef cnyali_lk
    freopen("cipher.in","r",stdin);
    freopen("cipher.out","w",stdout);
#endif
    generateData();
    cnt[0]=10000000;
    for(int i=1;i<=n+n;++i){
        cnt[i]=cnt[i-1];
        if(p[i])++cnt[i];
        else --cnt[i];
    }
    
    line=10000000;
    int ans1=0,ans2=0,ans3=0;
    for(int i=1;i<n+n;++i){
        if(p[i])
        add(cnt[i],1);
        else iadd(cnt[i],1);
        if(i>=n){
            if(p[i-n+1])add(cnt[i-n+1],-1);
            else{
                iadd(cnt[i-n+1],-1);
                if(count(cnt[i-n+1])==0)ans1=(i-n+1);
                if(count(cnt[i-n+1])==S)ans2=(i-n+1);
                if(icount(cnt[i-n+1])==S)ans3=(i-n+1);
            }
        }
    }
    printf("%d\n%d\n%d\n",ans1,ans2,ans3);

    return 0;
}

标签: 前缀和

添加新评论