本文主要是介绍hiho一下 第六十一周 题目1 : Combination Lock 线段树 成段更新，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
-
7 4 ABCDEFG CMD 1 2 5 C CMD 2 3 7 4 CMD 3 3 CMD 4 1 7
样例输出 -
HIMOFIN
描述
Finally, you come to the interview room. You know that a Microsoft interviewer is in the room though the door is locked. There is a combination lock on the door. There are N rotators on the lock, each consists of 26 alphabetic characters, namely, 'A'-'Z'. You need to unlock the door to meet the interviewer inside. There is a note besides the lock, which shows the steps to unlock it.
Note: There are M steps totally; each step is one of the four kinds of operations shown below:
Type1: CMD 1 i j X: (i and j are integers, 1 <= i <= j <= N; X is a character, within 'A'-'Z')
This is a sequence operation: turn the ith to the jth rotators to character X (the left most rotator is defined as the 1st rotator)
For example: ABCDEFG => CMD 1 2 3 Z => AZZDEFG
Type2: CMD 2 i j K: (i, j, and K are all integers, 1 <= i <= j <= N)
This is a sequence operation: turn the ith to the jth rotators up K times ( if character A is turned up once, it is B; if Z is turned up once, it is A now. )
For example: ABCDEFG => CMD 2 2 3 1 => ACDDEFG
Type3: CMD 3 K: (K is an integer, 1 <= K <= N)
This is a concatenation operation: move the K leftmost rotators to the rightmost end.
For example: ABCDEFG => CMD 3 3 => DEFGABC
Type4: CMD 4 i j(i, j are integers, 1 <= i <= j <= N):
This is a recursive operation, which means:
If i > j:Do Nothing Else:CMD 4 i+1 jCMD 2 i j 1For example: ABCDEFG => CMD 4 2 3 => ACEDEFG
输入
1st line: 2 integers, N, M ( 1 <= N <= 50000, 1 <= M <= 50000 )
2nd line: a string of N characters, standing for the original status of the lock.
3rd ~ (3+M-1)th lines: each line contains a string, representing one step.
输出
One line of N characters, showing the final status of the lock.
提示
Come on! You need to do these operations as fast as possible.
1.把区间全改成某个字符。
2.把区间全加上一个数。
3.把前几个字符移到最后面去。
4.把区间的所有的字符都加上1 2 3 ....;
对于1 2 4都是成段的更新字符串，所以可以用线段树来做，但每3个操作，我们可以把整个字符串，看成是一个环形的字符串，这样的话，我们只要改变了头的位置，就相当于移动了字符串的位置，复杂度o(1)完成，对于 1 2 4，可以这样设计线段树，定义node
struct node{
int sum,add,sadd,num,val;
};
分别表示，是否要全刷新为一个字符串，当前段要加的值，当前段要递增加的值，num为等差数的公差，也就是说，第一个，加上sadd ,第二个加上 sadd + num,第三个，加上sadd + 2 * num ,依此类推,由于等差数列加上一个等差数列，依然是一个等差数列，所以这里，可以 只用改动sadd num的值就可以表示一个等差数列的值了。val为当前的值。注意一个问题，就是第1个操作和第34操作是有时间的冲突的，也就是说1 和3 4 是有时间的对应的关系的，就应该先更新第1个操作的值，传递下去之后，才应该更新其它的操作。
总的复杂度为线段树的操作，o(m * log(n));
这里给出一些测试数据。可以说，向下传递的时候，这里是最复杂的。
7 7
ABCDEFG
CMD 3 3
CMD 4 1 7
CMD 1 2 5 C
CMD 2 3 7 4
CMD 3 2
CMD 1 2 5 C
CMD 2 3 7 4
3 2
AAA
CMD 1 1 3 C
CMD 2 1 3 1
#define N 50005
#define M 100005
#define maxn 205
#define MOD 1000000000000000007#define lson (now<<1)
#define rson (now<<1|1)
struct node{int sum,add,sadd,num,val;
};
node tree[N*8];
void update(int & x,int y){x += y;x %= 26;
}
void pushDown(int now,int l,int r){if(l == r){return ;}if(tree[now].sum >= 0){tree[lson].val = tree[lson].sum = tree[now].sum;tree[rson].val = tree[rson].sum = tree[now].sum;tree[now].sum = -1;tree[rson].add = tree[lson].add = 0;tree[rson].sadd = tree[lson].sadd = 0;tree[rson].num =tree[lson].num = 0;}if(tree[now].add >= 0){update(tree[lson].add,tree[now].add);update(tree[rson].add,tree[now].add);tree[now].add = 0;}if(tree[now].sadd >= 0){update(tree[lson].sadd,tree[now].sadd);update(tree[lson].num,tree[now].num);update(tree[rson].sadd,tree[now].sadd + ((r - l) / 2 + 1) * tree[now].num);update(tree[rson].num,tree[now].num);tree[now].sadd = 0;tree[now].num = 0;}
}
void buildTree(int l,int r,int now){tree[now].sum = -1;tree[now].val = 0;tree[now].add = tree[now].sadd = tree[now].num = 0;if(l >= r){return ;}int mid = (l+r)>>1;buildTree(l,mid,lson);buildTree(mid+1,r,rson);
}
void updateTree(int l,int r,int now,int s,int e,int c,int add){pushDown(now,l,r);if(s <= l && e>= r){if(c == 2){update(tree[now].add,add);}else if(c == 4){update(tree[now].sadd,l - s + add);update(tree[now].num,1);}else if(c == 1){tree[now].sum = add;tree[now].val = add;tree[now].add = tree[now].sadd = tree[now].num = 0;}return ;}int mid = (l+r)>>1;if(s <= mid) updateTree(l,mid,lson,s,e,c,add);if(e > mid) updateTree(mid+1,r,rson,s,e,c,add);
}
int queryTree(int l,int r,int now,int s,int e){pushDown(now,l,r);if(s <= l && e>= r){return (tree[now].val + tree[now].add + tree[now].sadd) % 26;}int mid = (l+r)>>1;if(s <= mid) return queryTree(l,mid,lson,s,e);if(e > mid) return queryTree(mid+1,r,rson,s,e);return 0;
}int n,m,q,k,top;
char str[N],str2[40];
void getSe(int s,int e,int & s1,int & e1,int & s2,int & e2){s--;e--;s1 = s2 = e1 = e2 = -2;int t1 = top + s,t2 = top + e;if(t1 < n && t2 < n){s1 = t1;e1 = t2;s2 = e2 = -2;}else if(t1 < n && t2 >= n){t2 %= n;s1 = t1;e1 = n - 1;s2 = 0;e2 = t2;}else if(t1 >= n && t2 >= n){t1 %= n;t2 %= n;s1 = t1;e1 = t2;s2 = e2 = -2;}s1++;e1++;s2++;e2++;
}
void outputStr(){int t = top;For(i,1,n+1){printf("%c",'A' + queryTree(1,n,1,t+1,t+1));t++;t %= n;}printf("\n");
}
int main()
{//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);while(S2(n,m)!=EOF){SS(str);top = 0;buildTree(1,n,1);FI(n){updateTree(1,n,1,i+1,i+1,1,str[i] - 'A');}FI(m){SS(str2);S(q);int s,e,s1,e1,s2,e2;if(q == 1){S2(s,e);SS(str2);getSe(s,e,s1,e1,s2,e2);updateTree(1,n,1,s1,e1,1,str2[0] - 'A');if(s2 != -1 && e2 != -1)updateTree(1,n,1,s2,e2,1,str2[0] - 'A');}else if(q == 2){S2(s,e);S(k);k %= 26;getSe(s,e,s1,e1,s2,e2);updateTree(1,n,1,s1,e1,2,k);if(s2 != -1 && e2 != -1)updateTree(1,n,1,s2,e2,2,k);}else if(q == 3){S(s);top += s;top %= n;}else if(q == 4){S2(s,e);getSe(s,e,s1,e1,s2,e2);updateTree(1,n,1,s1,e1,4,1);if(s2 != -1 && e2 != -1)updateTree(1,n,1,s2,e2,4,e1 - s1 + 2);}}outputStr();}//fclose(stdin);//fclose(stdout);return 0;
}
这篇关于hiho一下 第六十一周 题目1 : Combination Lock 线段树 成段更新的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
