首页 > 代码库 > （线段树区间合并）UVA 11235 - Frequent values
（线段树区间合并）UVA 11235 - Frequent values
题意：
一个数列，多次查询L到R最多连续相同数字的数量。
分析：
显然区间合并。不过还就没写了，都有点忘了。
不过回忆一下，push_down还是写对了。
不过WA了，后来仔细想一想，光查询光用已经维护的答案还不够，还需要在query的时候再合并一下，才能更新出正确的答案。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <vector> 6 7 8 using namespace std; 9 10 const int inf = 0x3f3f3f3f;11 const int maxn = 100010;12 13 struct Node {14 int left, right;15 int llen, rlen, zlen;16 int lval, rval;17 } node[maxn << 2];18 19 20 21 void push_up(int n) {22 node[n].llen = node[n << 1].llen;23 node[n].lval = node[n << 1].lval;24 node[n].rlen = node[n << 1 | 1].rlen;25 node[n].rval = node[n << 1 | 1].rval;26 if(node[n << 1].llen == node[n << 1].right - node[n << 1].left + 1 && node[n << 1].rval == node[n << 1 | 1].lval) {27 node[n].llen += node[n << 1 | 1].llen;28 }29 if(node[n << 1 | 1].rlen == node[n << 1 | 1].right - node[n << 1 | 1].left + 1 && node[n << 1].rval == node[n << 1 | 1].lval) {30 node[n].rlen += node[n << 1].rlen;31 }32 node[n].zlen = max(node[n << 1].zlen, node[n << 1 | 1].zlen);33 if(node[n << 1].rval == node[n << 1 | 1].lval) {34 node[n].zlen = max(node[n].zlen, node[n << 1].rlen + node[n << 1 | 1].llen);35 }36 }37 38 void build(int n, int left, int right) {39 node[n].left = left;40 node[n].right = right;41 if(left == right) {42 scanf("%d", &node[n].lval);43 node[n].rval = node[n].lval;44 node[n].llen = node[n].rlen = node[n].zlen = 1;45 return;46 }47 int mid = (left + right) >> 1;48 build(n << 1, left, mid);49 build(n << 1 | 1, mid + 1, right);50 push_up(n);51 }52 53 54 int query(int n, int left, int right) {55 if(node[n].left == left && node[n].right == right) {56 return node[n].zlen;57 }58 // printf("%d %d\n", node[n].left, node[n].right);59 int mid = (node[n].left + node[n].right) >> 1;60 int maxs = -1;61 if(mid >= right)maxs = max(maxs, query(n << 1, left, right));62 else if(mid < left)maxs = max(maxs, query(n << 1 | 1, left, right));63 else {64 int s = query(n << 1, left, mid);65 int t = query(n << 1 | 1, mid + 1, right);66 maxs = max(s, t);67 int ls = min(node[n << 1].rlen, mid - left + 1);68 int rs = min(node[n << 1 | 1].llen, right - mid);69 if(node[n << 1].rval == node[n << 1 | 1].lval) {70 maxs = max(maxs, ls + rs);71 }72 }73 // printf("--%d %d %d\n", node[n].left, node[n].right, maxs);74 return maxs;75 }76 77 int main() {78 #ifndef ONLINE_JUDGE79 // freopen("1.in", "r", stdin);80 // freopen("1.out", "w", stdout);81 #endif82 int n, q;83 while(~scanf("%d", &n) && n) {84 scanf("%d", &q);85 build(1, 1, n);86 // for(int i = 1; i <= 250; i++) {87 // printf("%d %d %d %d %d\n", node[i].left, node[i].right, node[i].llen, node[i].rlen, node[i].zlen);88 // }89 while(q--) {90 int l, r;91 scanf("%d%d", &l, &r);92 printf("%d\n", query(1, l, r));93 // puts("");94 }95 }96 return 0;97 98 }
（线段树区间合并）UVA 11235 - Frequent values
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。