[Petrozavodsk Summer-2014. Yandex Contest C]Supermutations

Solution

维护下标模5余0,1,2,3,4的位置的数字的区间和,记录每个数组当前的开头位置。
每个数组的开头位置是不同的!

Code

const int XN=1e5+11;

struct Arr {
    int off;
    long long sum[XN*2];

    long long Sum(int p,int x) {
        return sum[x/5+off+(x%5>p)];
    }

    long long Sum(int p,int l,int r) {
        return Sum(p,r)-Sum(p,l-1);
    }
}*a[5];

int main() {
//  freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n;std::cin>>n;
    for(int i=0;i<5;++i)
        a[i]=new Arr;
    for(int j=1;j<=n;++j) {
        for(int i=0;i<5;++i) {
            int x;std::cin>>x;
            a[i]->sum[j]=a[i]->sum[j+n]=x;
        }
    }
    for(int i=0;i<5;++i)
        for(int j=1;j<=n*2;++j)
            a[i]->sum[j]+=a[i]->sum[j-1];

    int m;std::cin>>m;
    while(m--) {
        char op;std::cin>>op;
        if(op=='?') {
            int l,r;std::cin>>l>>r;
            long long res=0;
            for(int i=0;i<5;++i)
                res+=a[i]->Sum(i,l,r);
            std::cout<<res<<'\n';
        } else if(op=='<') {
            int x;std::cin>>x;
            Arr *t[5];
            for(int i=0;i<5;++i) {
                (a[i]->off+=x/5+(x%5>i))%=n;
                t[i]=a[(i+x)%5];
            }
            for(int i=0;i<5;++i)
                a[i]=t[i];
        } else {
            int q[5];
            Arr *t[5];
            for(int i=0;i<5;++i) {
                std::cin>>q[i];
                t[i]=a[--q[i]];
            }
            for(int i=0;i<5;++i)
                a[i]=t[i];
        }
    }


    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注