hihor学习日记：hiho一下 第六十一周
http://hihocoder.com/contest/hiho61/problem/1
题意分析
给定一个字符串s，以及对该字符串s的 m 个操作。
字符串s包含n个字符，下标为1…n。字符由’A’到’Z’构成，字符增加1表示该字符变为后续字符，比如’A’增加1是’B’，‘C’增加1是’D’。需要注意的是’Z’增加1是’A’。
m个操作包含以下四种类型：
将字符串第i位到第j位设定为C。
比如当i=2,j=3,C='Z’时：“ABCDEFG"变成"AZZDEFG”
将字符串第i位到第j位增加K。
比如i=2,j=3,K=1时：“ABCDEFG"变成"ACDDEFG”
将字符串左边K位移至右边。
比如K=3时：“ABCDEFG"变成"DEFGABC”
从字符串第i位到第j位，依次增加1,2,…,j-i+1。
比如当i=2,j=3时：“ABCDEFG"变成"ACEDEFG”
输出m个操作结束后的字符串s。
算法分析
本题需要根据每一次的操作去修改现在的s。若采用朴素的做法，每一次修改其最大代价为O(n)，故总的时间复杂度为O(nm)。对于n=50000,m=50000的数据量来说，这样时间复杂度显然是不能够接受的。
仔细观察我们每一次的操作，其中CMD3是对整体进行了平移，CMD1,CMD2,CMD4都是针对i到j的一个区间进行操作。
首先我们来解决看似比较简单的CMD3操作：
若将整个字符串s看作环形，则线型的字符串是从起点指针SP开始顺时针将n个元素进行展开得到的。那么CMD3操作为顺时针移动该环的头指针。举个例子来说：
最开始头指针在1时，我们展开字符串为[1,2,3,4,5]。当执行CMD3 K=2操作后，起点指针SP移动到3的位置，此时展开的字符串为[3,4,5,1,2]。
符合CMD3操作的规则，并且起点指针SP的改变就是增加了K。
其中新字符串的第ij位，对应的是原字符串第i+SPj+SP位。
所以我们只需要维护一个SP指针，当执行CMD3操作时，改变SP的值。而对于其他操作的区间，只需要将区间从[i…j]变化到[i+SP…j+SP]即可。
需要注意的是，SP,i+SP,j+SP有可能会超过n。当超过n时，需要将其值减去n。
至此执行CMD3操作的时间复杂度降至O(1)。
接下来考虑CMD1,CMD2,CMD4。这三个操作均为区间上的操作，因此我们可以使用线段树来进行模拟。(在我们的Hiho一下第19期和第20期可以找到线段树的教程)
在那之前，我们需要对字符进行处理。从题目中我们知道当一个字符超过’Z’时，会直接变成’A’。所以我们可以直接考虑将’A’'Z’与025对应起来。当一个字符增加了很多次K后，其实际表示的字符也就等于该值 mod 26。
构造线段树
构造线段树，主要是构造每个节点的数据域，使其能够记录我们需要的信息，同时在父节点和子节点之间能够进行信息的传递。根据本题的题意，我们构造的线段树其节点包含以下三个数据：
same: 表示当前区间的字符是否相同，若相同则same等于该字符，否则same=-1
add: 表示当前区间的增量，对应CMD2操作所增加的K
delta和 inc : 这两个变量是一组，其表示CMD4的操作。其含义为，该区间最左起第1个元素值增量为delta，此后每一个元素的增量比前一个多inc。即第2个元素的增量为delta+inc，第3个元素的增量为delta+inc+inc，…，第i个元素的增量为delta+inc*(i-1)。举个例子：
若我们对区间[1,3]进行了CMD4操作，实际的意义为s1+1,s[2]+2,s[3]+3。对于表示区间[1,3]的节点，其Delta=1,inc=1。
若我们对区间[1,3]进行了2次CMD4操作，实际意义为s1+2,s[2]+4,s[3]+6。则此时Delta=2,inc=2。而对于表示区间[2,3]的节点，其Delta=4,inc=2。因为该区间左起第1个元素为s[2]+4，故delta=4。
在本题中我们一开始便读入了字符串，该字符串的每一个字符对应了树的一个叶子节点。故我们一开始就需要建出整颗树，其代码：
// 该段代码我们采用的是数组模拟线段树
const int MAXN = 50001;
struct sTreeNode {
int left, right;
int same, add;
int delta, inc;
int lch, rch;
} tree[ MAXN << 2 ];
void createTree(int rt, int left, int right) {
tree[rt].left = left, tree[rt].right = right;
tree[rt].delta = tree[rt].step = 0;
tree[rt].add = 0;
if (left == right) { // 叶子节点
tree[rt].base = str[ left ] - 'A';
tree[rt].lch = tree[rt].rch = 0;
return ;
}
// 非叶子节点
tree[rt].base = -1;
tree[rt].lch = rt * 2, tree[rt].rch = rt * 2 + 1;
int mid = (tree[rt].left + tree[rt].right) >> 1;
createTree(tree[rt].lch, left, mid);
createTree(tree[rt].rch, mid + 1, right);
return ;
}
更新线段树
在更新线段树时，需要注意更新区间可能会出现i+SP <= n并且j+SP大于n时，此时要将区间分为[i+SP…n]和[1…j+SP-n]两个部分单独处理。
更新线段树信息的update函数：
// rt表示当前节点
// left,right表示此次操作的区间
// key表示此次操作K或Delta
// type表示此次操作的类型
void update(int rt, int left, int right, int key, int type) {
if (!rt) return ;
if (tree[rt].right < left || tree[rt].left > right) return ;
if (left <= tree[rt].left && tree[rt].right <= right) {
// 当前节点区间完全包含于[left,right]
// 更新当前区间信息
...
} else {
// 当前节点区间不完全包含于[left,right]，则需要让子区间来处理
// 传递当前区间的信息
...
// 更新当前区间信息
...
// 迭代处理
update(tree[rt].lch, left, right, key, type);
update(tree[rt].rch, left, right, key, type);
}
return ;
}
若当前区间包含于[left,right]，根据操作的不同我们进行如下的处理：
CMD1: 直接更新区间的same值，同时将add，delta和inc置为0
if (type == 1) {
tree[rt].same = key;
tree[rt].delta = 0, tree[rt].inc = 0;
tree[rt].add = 0;
}
CMD2: 累加到当前区间的add上
if (type == 2) {
tree[rt].add += key;
}
CMD4: 将新的delta和inc累加到当前区间的delta和inc上
if (type == 4) {
tree[rt].delta += key + (tree[rt].left - left);
tree[rt].inc ++;
}
当需要对子区间进行处理时，我们需要将当前区间的信息传递下去，此时需要判断当前区间的same值：
// 传递当前区间的信息
int mid = (tree[rt].left + tree[rt].right) / 2;
if (tree[rt].base == -1) {
// lch
tree[ tree[rt].lch ].delta += tree[rt].delta;
tree[ tree[rt].lch ].step += tree[rt].step;
tree[ tree[rt].lch ].add += tree[rt].add;
// rch
tree[ tree[rt].rch ].delta += tree[rt].delta + (mid - tree[rt].left + 1) * tree[rt].step;
tree[ tree[rt].rch ].step += tree[rt].step;
tree[ tree[rt].rch ].add += tree[rt].add;
} else {
tree[ tree[rt].lch ].base = tree[ tree[rt].rch ].base = tree[rt].base;
tree[ tree[rt].lch ].delta = tree[rt].delta;
tree[ tree[rt].rch ].delta = tree[rt].delta + (mid - tree[rt].left + 1) * tree[rt].step;
tree[ tree[rt].lch ].step = tree[ tree[rt].rch ].step = tree[rt].step;
tree[ tree[rt].lch ].add = tree[ tree[rt].rch ].add = tree[rt].add;
}
当我们把当前区间的信息传递下去后，可以知道当前区间内的字符一定会发生改变，所以设置其same=1。同时由于当前区间的add，delta和inc信息已经传递下去，其本身的add，delta和inc设置为0：
// 更新当前区间信息
tree[rt].base = -1;
tree[rt].delta = tree[rt].step = 0;
tree[rt].add = 0;
产生新的字符串
在这一步我们需要对整个线段树进行一次遍历，将所有的信息传递到叶子节点，再根据叶子节点的值产生我们新的字符串。
int f[ MAXN ]; // 记录每个叶子节点的数值
void getResult(int rt) {
if (!rt) return ;
if (tree[rt].base != -1) {
int delta = tree[rt].delta;
for (int i = tree[rt].left; i <= tree[rt].right; ++i)
f[i] = tree[rt].base + tree[rt].add + delta, delta += tree[rt].step;
} else {
int mid = (tree[rt].left + tree[rt].right) / 2;
// lch
tree[ tree[rt].lch ].delta += tree[rt].delta;
tree[ tree[rt].lch ].step += tree[rt].step;
tree[ tree[rt].lch ].add += tree[rt].add;
// rch
tree[ tree[rt].rch ].delta += tree[rt].delta + (mid - tree[rt].left + 1) * tree[rt].step;
tree[ tree[rt].rch ].step += tree[rt].step;
tree[ tree[rt].rch ].add += tree[rt].add;
getResult(tree[rt].lch);
getResult(tree[rt].rch);
}
return ;
}
此时得到的s并不是我们最后的结果，还需要根据SP的值来输出
void typeAns() {
for (int i = 0; i < n; ++i)
printf("%c", (char) (f[(SP + i) % n] + 'A'));
printf("\n");
return ;
}
结果分析
本题现场的通过率为2%，一个有9名选手。
本题的思维复杂度并没有第三题高，但是代码量比较大。因此在前三题花费了较多精力的选手很难有足够的时间来解决此题。
不过也有少数选手选择放弃了第三题，直接从第四题入手并得到了满分。
对于实际比赛来说，当拿到第四题这样的题目，而时间又不足够充裕时，直接采用朴素算法获得部分分也是一个较好的选择。
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int Mod = 1e9 + 7;
const int maxn = 1e5 + 5;
const double eps = 0.00000001;
const int INF = 0x3f3f3f3f;
struct Tree{
LL same, add;
LL delte, inc;
int l, r;
int w;
}tree[maxn << 2];
string ss;
void creatTree(int k, int l, int r) {
tree[k].l = l; tree[k].r = r;
tree[k].delte = tree[k].add = tree[k].inc = 0;
if(l == r) {
tree[k].w = ss[l - 1] - 'A';
return ;
}
tree[k].w = -1;
int mid = (l + r) >> 1;
creatTree(k << 1, l, mid);
creatTree(k << 1 | 1, mid + 1, r);
}
void down(int rt) {
int mid = (tree[rt].l + tree[rt].r) >> 1;
if(tree[rt].w == -1) {
tree[rt << 1].delte += tree[rt].delte;
tree[rt << 1].inc += tree[rt].inc;
tree[rt << 1].add += tree[rt].add;
tree[rt << 1 | 1].delte += tree[rt].delte + (mid - tree[rt].l + 1) * tree[rt].inc;
tree[rt << 1 | 1].inc += tree[rt].inc;
tree[rt << 1 | 1].add += tree[rt].add;
}else {
tree[rt << 1].w = tree[rt << 1 | 1].w = tree[rt].w;
tree[rt << 1].delte = tree[rt].delte;
tree[rt << 1 | 1].delte = tree[rt].delte + (mid - tree[rt].l + 1) * tree[rt].inc;
tree[rt << 1].inc = tree[rt << 1 | 1].inc = tree[rt].inc;
tree[rt << 1].add = tree[rt << 1 | 1].add = tree[rt].add;
}
tree[rt].w = -1;
tree[rt].delte = tree[rt].inc = 0;
tree[rt].add = 0;
}
void update(int rt, int l, int r, LL key, int type) {
//cout << tree[rt].l << " " << tree[rt].r << " " << l << " " << r << endl;
if(!rt)return ;
if(tree[rt].r < l || tree[rt].l > r) return ;
if(tree[rt].l >= l && tree[rt].r <= r) {
if(type == 1) {
tree[rt].w = key;
tree[rt].delte = 0;
tree[rt].inc = 0;
tree[rt].add = 0;
}else if(type == 2) {
tree[rt].add += key;
}else if(type == 4) {
tree[rt].delte += key + (tree[rt].l - l);
tree[rt].inc ++;
}
}else {
int mid = (tree[rt].l + tree[rt].r) >> 1;
down(rt);
//cout << tree[rt].l << " " << tree[rt].r << " " << mid << endl;
update(rt << 1, l, r, key, type);
update(rt << 1 | 1, l, r, key, type);
}
}
int f[maxn];
void getResult(int rt) {
if(!rt) return ;
if(tree[rt].w != -1) {
int delte = tree[rt].delte;
for (int i = tree[rt].l; i <= tree[rt].r; i ++) {
f[i] = tree[rt].w + tree[rt].add + delte;
f[i] %= 26;
delte += tree[rt].inc;
}
}else {
down(rt);
getResult(rt << 1);
getResult(rt << 1 | 1);
}
return ;
}
int SP;
int n, op;
void typeAns() {
for (int i = 1; i <= n; i ++) {
char m;
if((SP + i) > n) m = f[SP + i - n] + 'A';
else m = f[SP + i] + 'A';
cout << m;
}
cout << endl;
return ;
}
int main()
{
while(scanf("%d %d", &n, &op) != EOF) {
cin >> ss;
string st;
creatTree(1, 1, n);
while(op --) {
cin >> st;
int type;
cin >> type;
if(type == 3) {
int k;
cin >> k;
SP = (SP + k) % n;
}else if(type == 1) {
int l, r;
char m;
cin >> l >> r >> m;
int key = m - 'A';
l += SP;
while(l > n) l -= n;
r += SP;
while(r > n) r -= n;
//cout << l << " " << r << endl;
if(l <= r) {
update(1, l, r, key, type);
}else {
update(1, l, n, key, type);
update(1, 1, r, key, type);
}
}else if(type == 2) {
int l, r;
LL key;
cin >> l >> r >> key;
l += SP; r += SP;
while(l > n) l -= n;
while(r > n) r -= n;
//cout << l << " " << r << endl;
if(l <= r) {
update(1, l, r, key, type);
}else {
update(1, l, n, key, type);
update(1, 1, r, key, type);
}
}else if(type == 4) {
int l, r;
cin >> l >> r;
LL key = 1;
l += SP; r += SP;
while(l > n) l -= n;
while(r > n) r -= n;
//cout << l << " " << r << endl;
if(l <= r) {
update(1, l, r, key, type);
}else {
update(1, l, n, key, type);
update(1, 1, r, key + n - l + 1, type);
}
}
//cout << SP << endl;
}
getResult(1);
typeAns();
}
return 0;
}