题目大意
给定N个字符，范围为A-Z，编号为1-N，对该字符序列进行M个操作，操作有4中类型：
（1）CMD 1 i j X
将[i, j]区间内的字符均变为X
（2）CMD 2 i j K
将[i, j]区间内的字符均增加K，如果超过Z，则再从A开始循环。
（3）CMD 3 K
将字符序列中最左端的K个字符移动到最右端
（4）CMD 4 i j
进行一个递归操作：
if i > j
return;
else
CMD 4 i+1 j
CMD 2 i j
endif
题目分析
对区间进行操作，考虑使用线段树，CMD 1， 2很容易通过线段树解决，但是对于CMD 3，可以进行转换一下：CMD 3并不直接对线段树的叶子节点上的元素进行移动（复杂度太高），而是记录一个偏移量offset，当CMD 3之后再进行其他操作时，将其他操作的区间[i, j]映射到添加偏移量之后的区间[(i + offset)%N, (j + offset)%N]，当然，如果 (i + offset)%N > (j + offset)%N，则需要分两个部分进行求解 [0, j]和[i, N-1]。在最后输出字符串时候，再根据最后的offset来定位到元素实际的位置。
对于CMD 4，可以发现它的实际效果是将[i, j]区间内的数字，s[i] + 1， s[i+2] + 2, s[i+2] + 3.... 那么，对于线段树的节点，维护一个delta和一个inc，delta表示该区间的首位元素由于CMD 4的操作需要增加的量为delta，而inc表示该区间相邻元素a1，a2由于CMD 4而使得a2比a1增加inc。
因此用线段树来求解时，用以下信息来记录线段树节点的状态：
(1) value 默认为-1， 如果大于等于0，表示该节点代表的区间内的值均为 value
(2) add 默认为0， 如果不等于0，表示该节点代表区间内的值均增加add
(3) delta 默认为0，如果不等于0，表示该节点代表区间内最左端元素由于CMD 4需要增加的量
(4) inc 默认为0，如果不为0，表示该节点代表区间内相邻元素之间增量相差inc.
实现
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define MAX(a,b) (a > b? a:b)
#define MIN(a,b) (a < b? a:b) struct Node {
int beg, end;
int value; //该区间的所有值均为 'A' + value， 若value为-1，为无效
int add; //该区间所有的值均增加add
int delta; //对应操作CMD4， 表示区间最左端的元素增加的数值
int inc; //对应操作CMD4， 表示区间从最左端到最右端当前元素比前一个元素增加的数值
Node() {
beg = end = add = delta = inc = 0;
value = -1;
}
};
char gSeq[50005];
Node gNodes[200005];
void BuildTree(int node, int beg, int end) {
gNodes[node].beg = beg;
gNodes[node].end = end; if (beg == end) {
gNodes[node].value = gSeq[beg] - 'A';
return;
}
int left = 2 * node + 1;
int right = 2 * node + 2;
int mid = (beg + end) / 2;
BuildTree(left, beg, mid);
BuildTree(right, mid + 1, end);
}
int gPoint = 0;
int N; //sequence length
void PushDown(int node) {
if (gNodes[node].beg == gNodes[node].end) {
return;
}
int left = 2 * node + 1, right = 2 * node + 2;
if (gNodes[node].value >= 0) {
//如果node的value大于0，说明之前曾经被赋值过，那么node的 add，delta，inc等如果不为0，则都是在赋值value之后
//进行的操作
gNodes[left].value = gNodes[right].value = gNodes[node].value;
gNodes[left].add = gNodes[right].add = gNodes[node].add;
gNodes[left].delta = gNodes[node].delta;
gNodes[right].delta = (gNodes[left].end - gNodes[left].beg + 1)*gNodes[node].inc + gNodes[node].delta;
gNodes[left].inc = gNodes[right].inc = gNodes[node].inc;
}
else{
gNodes[left].add += gNodes[node].add;
gNodes[right].add += gNodes[node].add;
if (gNodes[node].delta){
gNodes[left].delta += gNodes[node].delta;
gNodes[right].delta += (gNodes[left].end - gNodes[left].beg + 1)*gNodes[node].inc + gNodes[node].delta;
gNodes[right].inc += gNodes[node].inc;
gNodes[left].inc += gNodes[node].inc;
}
}
gNodes[node].value = -1;
gNodes[node].add = gNodes[node].delta = gNodes[node].inc = 0;
}
void Action(int node, int beg, int end, int cmd, int k){
if (beg > end)
return;
if (gNodes[node].beg == beg && gNodes[node].end == end){
if (cmd == 1){
gNodes[node].value = k;
gNodes[node].add = gNodes[node].delta = gNodes[node].inc = 0;
}
else if (cmd == 2){
gNodes[node].add += k;
}
else if (cmd == 4){
gNodes[node].delta += k;
gNodes[node].inc++;
}
return;
}
PushDown(node);
int mid = (gNodes[node].beg + gNodes[node].end) / 2;
int left = 2 * node + 1, right = 2 * node + 2;
if (beg > mid){
Action(right, beg, end, cmd, k);
}
else if (end <= mid){
Action(left, beg, end, cmd, k);
}
else{
Action(left, beg, mid, cmd, k);
if (cmd == 4)
k += mid - beg + 1;
Action(right, mid + 1, end, cmd, k);
}
}
void Query(int node) {
if (gNodes[node].beg == gNodes[node].end) {
int index = ((gNodes[node].beg - gPoint) % N + N) % N;
gSeq[index] = 'A' + ((gNodes[node].value + gNodes[node].add + gNodes[node].delta) % 26 + 26) % 26;
return;
}
int left = 2 * node + 1, right = 2 * node + 2;
if (gNodes[node].value >= 0) {
//如果node的value大于0，说明之前曾经被赋值过，那么node的 add，delta，inc等如果不为0，则都是在赋值value之后
//进行的操作
gNodes[left].value = gNodes[right].value = gNodes[node].value;
gNodes[left].add = gNodes[right].add = gNodes[node].add;
gNodes[left].delta = gNodes[node].delta;
gNodes[right].delta = (gNodes[left].end - gNodes[left].beg + 1)*gNodes[node].inc + gNodes[node].delta;
gNodes[left].inc = gNodes[right].inc = gNodes[node].inc;
}
else{
gNodes[left].add += gNodes[node].add;
gNodes[right].add += gNodes[node].add;
if (gNodes[node].delta){
gNodes[left].delta += gNodes[node].delta;
gNodes[right].delta += (gNodes[left].end - gNodes[left].beg + 1)*gNodes[node].inc + gNodes[node].delta;
gNodes[right].inc += gNodes[node].inc;
gNodes[left].inc += gNodes[node].inc;
}
}
gNodes[node].value = -1;
gNodes[node].add = gNodes[node].delta = gNodes[node].inc = 0;
Query(left);
Query(right); } int main() {
int m;
char tmp[5];
int cmd, i, j, k;
char c;
scanf("%d %d", &N, &m);
getchar();
scanf("%s", gSeq);
BuildTree(0, 0, N - 1);
getchar();
for (int t = 0; t < m; t++) {
scanf("%s %d", tmp, &cmd);
if (cmd == 1) {
scanf("%d %d %c", &i, &j, &c);
i = ((i - 1 + gPoint) % N + N) % N;
j = ((j - 1 + gPoint) % N + N) % N;
if (i > j) {
Action(0, 0, j, 1, c - 'A');
Action(0, i, N - 1, 1, c - 'A');
}
else
Action(0, i, j, 1, c - 'A');
}
else if (cmd == 2) {
scanf("%d %d %d", &i, &j, &k);
i = ((i - 1 + gPoint) % N + N) % N;
j = ((j - 1 + gPoint) % N + N) % N;
if (i > j) {
Action(0, 0, j, 2, k);
Action(0, i, N - 1, 2, k);
}
else
Action(0, i, j, 2, k);
}
else if (cmd == 3) {
scanf("%d", &k);
gPoint += k;
}
else if (cmd == 4) {
scanf("%d %d", &i, &j);
i = ((i - 1 + gPoint) % N + N) % N;
j = ((j - 1 + gPoint) % N + N) % N;
if (i > j) {
Action(0, 0, j, 4, N - i + 1);
Action(0, i, N - 1, 4, 1);
}
else
Action(0, i, j, 4, 1);
}
//Query(0);
//printf("%s\n", gSeq);
getchar();
}
Query(0);
printf("%s\n", gSeq);
return 0;
}