首页 > 代码库 > （线段树区间赋值）CSU 1942 - Sort String
（线段树区间赋值）CSU 1942 - Sort String
题意：
一个串（串中只有26个小写字母），选一个区间进行排序，进行100000次，输出最后的串。
分析：
比赛的时候很懵逼，感觉这题跟之前的额大崩龙有点像，但是没多想，也怪自己太菜了。
确实是真的像，甚至是一模一样啊。
对于每次排序只需要进行一次类似计数排序的的操作即可，26个字符，进行26次区间赋值即可。理论上时间能过得去。
代码：
1 #include <queue> 2 #include <string> 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 #include <algorithm> 7 #include <map> 8 9 10 using namespace std; 11 12 typedef long long ll; 13 typedef unsigned long long ull; 14 typedef pair<int, int> pii; 15 typedef pair<ull, ull> puu; 16 17 #define inf (0x3f3f3f3f) 18 #define lnf (0x3f3f3f3f3f3f3f3f) 19 #define eps (1e-8) 20 #define fi first 21 #define se second 22 23 //-------------------------- 24 25 const ll mod = 1000000007; 26 const int maxn = 100010; 27 28 29 char str[maxn]; 30 int n; 31 int q; 32 33 struct Node { 34 int left, right; 35 int num[26]; 36 int lazy; 37 } node[maxn << 2]; 38 39 void push_up(int n) { 40 for(int i = 0; i < 26; i++) { 41 node[n].num[i] = node[n << 1].num[i] + node[n << 1 | 1].num[i]; 42 } 43 } 44 45 void push_down(int n) { 46 if(node[n].lazy != -1) { 47 node[n << 1].lazy = node[n << 1 | 1].lazy = node[n].lazy; 48 memset(node[n << 1].num, 0, sizeof(node[n << 1].num)); 49 memset(node[n << 1 | 1].num, 0, sizeof(node[n << 1 | 1].num)); 50 node[n << 1].num[node[n].lazy] = (node[n].right - node[n].left + 1) - (node[n].right - node[n].left + 1) / 2; 51 node[n << 1 | 1].num[node[n].lazy] = (node[n].right - node[n].left + 1) / 2; 52 node[n].lazy = -1; 53 } 54 } 55 56 void update(int n, int left, int right, char val) { 57 if(node[n].left >= left && node[n].right <= right) { 58 node[n].lazy = val - ‘a‘; 59 memset(node[n].num, 0, sizeof(node[n].num)); 60 node[n].num[node[n].lazy] = node[n].right - node[n].left + 1; 61 return ; 62 } 63 push_down(n); 64 int mid = (node[n].left + node[n].right) >> 1; 65 if(mid >= left)update(n << 1, left, right, val); 66 if(mid < right)update(n << 1 | 1, left, right, val); 67 push_up(n); 68 } 69 70 int query(int n, int left, int right, char val) { 71 if(node[n].left >= left && node[n].right <= right) { 72 return node[n].num[val - ‘a‘]; 73 } 74 push_down(n); 75 int mid = (node[n].left + node[n].right) >> 1; 76 int sum = 0; 77 if(mid >= left)sum += query(n << 1, left, right, val); 78 if(mid < right)sum += query(n << 1 | 1, left, right, val); 79 return sum; 80 } 81 82 83 void build(int n, int left, int right) { 84 node[n].left = left; 85 node[n].right = right; 86 node[n].lazy = -1; 87 if(left == right) { 88 node[n].num[str[left] - ‘a‘] = 1; 89 return ; 90 } 91 int mid = (left + right) >> 1; 92 build(n << 1, left, mid); 93 build(n << 1 | 1, mid + 1, right); 94 push_up(n); 95 } 96 97 void print(int n) { 98 if(node[n].left == node[n].right) { 99 for(int i = 0; i < 26; i++) {100 if(node[n].num[i] != 0) {101 printf("%c", i + ‘a‘);102 break;103 }104 }105 return ;106 }107 push_down(n);108 print(n << 1);109 print(n << 1 | 1);110 }111 112 void solve() {113 while(~scanf("%d%d", &n, &q)) {114 memset(node, 0, sizeof(node));115 scanf("%s", str + 1);116 build(1, 1, n);117 while(q--) {118 int l, r, op;119 scanf("%d%d%d", &l, &r, &op);120 int num[26] = {0};121 for(int i = 0; i < 26; i++) {122 num[i] = query(1, l, r, i + ‘a‘);123 }124 if(op == 1) {125 for(int i = 0; i < 26; i++) {126 if(num[i] > 0) {127 update(1, l, l + num[i] - 1, i + ‘a‘);128 l += num[i];129 }130 }131 } else {132 for(int i = 25; i >= 0; i--) {133 if(num[i] > 0) {134 update(1, l, l + num[i] - 1, i + ‘a‘);135 l += num[i];136 }137 }138 }139 }140 print(1);141 puts("");142 }143 144 145 146 }147 148 int main() {149 #ifndef ONLINE_JUDGE150 freopen("1.in", "r", stdin);151 freopen("1.out", "w", stdout);152 #endif153 solve();154 return 0;155 }
（线段树区间赋值）CSU 1942 - Sort String
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。