Petrozavodsk Summer-2014. Yandex Contest C.Supermutations
题目大意
给你一个长度为 $5 \cdot n$ 的序列，有三个操作：
- 将每个五元组中的元素按照输入的排列进行重排。
- 将所有数左移，原先靠左的粘贴到序列后面
- 求 $[l, r]$ 的和
题目分析
将所有的元素按照对 $5$ 取模的结果分成五组分别维护区间和，再用一个五元组记录下每组数的顺序，第一个操作交换的时候直接操作这个五元组即可。对于左移操作需要分别记录下每组数的偏移量，而且这对五元组的顺序也有影响，应重新计算。查询时对每一组进行分别查询处理即可。
代码
（代码为比赛的时候写的线段树，其实用前缀和维护即可）
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int a[6][maxn];
int n, m;
struct node {
int l, r;
int lc, rc;
int sum;
};
struct st {
int tc;
int root;
int p;
node tree[maxn];
int query_tree(int pos, int l, int r){
int mid = (tree[pos].l + tree[pos].r) / 2;
if(tree[pos].l == l and r == tree[pos].r){
return tree[pos].sum;
}
if(r <= mid){
return query_tree(tree[pos].lc, l, r);
}else if(l <= mid){
return query_tree(tree[pos].lc, l, mid) + query_tree(tree[pos].rc, mid + 1, r);
}else{
return query_tree(tree[pos].rc, l, r);
}
}
int init_tree(int l, int r){
int mid = (l + r) / 2;
int pos = ++tc;
tree[pos].l = l;
tree[pos].r = r;
if(l == r){
tree[pos].sum = a[p][l];
}else{
tree[pos].lc = init_tree(l, mid);
tree[pos].rc = init_tree(mid + 1, r);
tree[pos].sum = tree[tree[pos].lc].sum + tree[tree[pos].rc].sum;
}
return pos;
}
int query(int l, int r){
return query_tree(root, l, r);
}
int init(int x){
tc = 0;
p = x;
root = init_tree(1, n);
return 0;
}
};
st tree[6];
int main(){
int i, j;
int l, r;
int x, y;
int p[] = {0, 1, 2, 3, 4, 5};
int pb[10];
int opt[10];
int c[6] = {0};
char ch;
scanf("%d", &n);
for(i=1;i<=n;i++){
for(j=1;j<=5;j++){
scanf("%d", &a[j][i]);
}
}
tree[1].init(1);
tree[2].init(2);
tree[3].init(3);
tree[4].init(4);
tree[5].init(5);
scanf("%d", &m);
while(m--){
scanf(" %c", &ch);
if(ch == '?'){
scanf("%d%d", &l, &r);
int ans = 0;
for(i=1;i<=5;i++){
x = l / 5 + (l % 5 != 0);
if((l - 1) % 5 + 1 > i){
x++;
}
y = r / 5 + (r % 5 != 0);
if((r - 1) % 5 + 1 < i){
y--;
}
if(x <= y){
if(y + c[p[i]] <= n){
ans += tree[p[i]].query(x + c[p[i]], y + c[p[i]]);
}else if(x + c[p[i]] <= n){
ans += tree[p[i]].query(x + c[p[i]], n) + tree[p[i]].query(1, (y + c[p[i]]) % n);
}else{
ans += tree[p[i]].query((x + c[p[i]]) % n, (y + c[p[i]]) % n);
}
}
}
printf("%dn", ans);
}else if(ch == '<'){
scanf("%d", &x);
for(i=1;i<=5;i++){
c[p[i]] = (c[p[i]] + x / 5 + (x % 5 >= i)) % n;
pb[i] = p[(i + x % 5 - 1) % 5 + 1];
}
for(i=1;i<=5;i++){
p[i] = pb[i];
}
}else if(ch == '#'){
for(i=1;i<=5;i++){
scanf("%d", &opt[i]);
}
for(i=1;i<=5;i++){
pb[i] = p[opt[i]];
}
for(i=1;i<=5;i++){
p[i] = pb[i];
}
}
}
return 0;
}