首页 > 代码库 > AC日记——Periodic RMQ Problem codeforces 803G
AC日记——Periodic RMQ Problem codeforces 803G
G - Periodic RMQ Problem
思路:
题目给一段序列,然后序列复制很多次;
维护序列很多次后的性质;
线段树动态开点;
来,上代码:
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define maxn 100005struct TreeNodeType { int l, r, mid, min, flag; TreeNodeType *lc, *rc; TreeNodeType() { flag=0; lc = NULL; rc = NULL; }};struct TreeNodeType *root, *rot;int n, k, m;inline void in(int &now){ char Cget = getchar(); now = 0; while (Cget > ‘9‘ || Cget < ‘0‘) Cget = getchar(); while (Cget >= ‘0‘&&Cget <= ‘9‘) { now = now * 10 + Cget - ‘0‘; Cget = getchar(); }}void tree_build_ori(TreeNodeType *&now, int l, int r){ if (now == NULL) { now = new TreeNodeType; now->l = l, now->r = r; now->mid = (l + r) >> 1; } if (l == r) { in(now->min); return; } tree_build_ori(now->lc, l, now->mid); tree_build_ori(now->rc, now->mid + 1, r); now->min = min(now->lc->min, now->rc->min);}int tree_query_ori(TreeNodeType *&now, int l, int r){ if (now->l == l&&now->r == r) return now->min; if (l > now->mid) return tree_query_ori(now->rc, l, r); else if (r <= now->mid) return tree_query_ori(now->lc, l, r); else return min(tree_query_ori(now->lc, l, now->mid), tree_query_ori(now->rc, now->mid + 1, r));}inline void tree_down(TreeNodeType *&now){ now->lc->min = now->flag; now->lc->flag = now->flag; now->rc->min = now->flag; now->rc->flag = now->flag; now->flag = 0;}int solve(int l, int r){ if(r-l+1>=n) return rot->min; l%=n,r%=n; if(l==0) l=n; if(r==0) r=n; if(r<l) return min(tree_query_ori(rot, l, n), tree_query_ori(rot, 1, r)); else return tree_query_ori(rot,l,r);}void tree_change(TreeNodeType *&now, int l, int r, int x){ if (now->l == l&&now->r == r) { now->min = x; now->flag = x; return; } if (now->rc == NULL) { now->rc = new TreeNodeType; now->rc->l = now->mid + 1; now->rc->r = now->r; now->rc->mid = (now->rc->r + now->rc->l) >> 1; now->rc->min = solve(now->rc->l, now->rc->r); } if (now->lc == NULL) { now->lc = new TreeNodeType; now->lc->l = now->l; now->lc->r = now->mid; now->lc->mid = (now->lc->l + now->lc->r) >> 1; now->lc->min = solve(now->lc->l, now->lc->r); } if (now->flag) tree_down(now); if (l > now->mid) tree_change(now->rc, l, r, x); else if (r <= now->mid) tree_change(now->lc, l, r, x); else { tree_change(now->lc, l, now->mid, x); tree_change(now->rc, now->mid + 1, r, x); } now->min = min(now->lc->min, now->rc->min);}int tree_query(TreeNodeType *&now, int l, int r){ if (now->l == l&&now->r == r) return now->min; if (now->rc == NULL) { now->rc = new TreeNodeType; now->rc->l = now->mid + 1; now->rc->r = now->r; now->rc->mid = (now->rc->r + now->rc->l) >> 1; now->rc->min = solve(now->rc->l, now->rc->r); } if (now->lc == NULL) { now->lc = new TreeNodeType; now->lc->l = now->l; now->lc->r = now->mid; now->lc->mid = (now->lc->l + now->lc->r) >> 1; now->lc->min = solve(now->lc->l, now->lc->r); } if (now->flag) tree_down(now); if (l > now->mid) return tree_query(now->rc, l, r); else if (r <= now->mid) return tree_query(now->lc, l, r); else return min(tree_query(now->lc, l, now->mid), tree_query(now->rc, now->mid + 1, r)); now->min = min(now->lc->min, now->rc->min);}int main(){ root = NULL, rot = NULL; int op, l, r, x; in(n), in(k), tree_build_ori(rot, 1, n), in(m); root = new TreeNodeType; root->l = 1, root->r = n*k, root->mid = 1 + n*k >> 1, root->min = rot->min; for (; m--;) { in(op), in(l), in(r); if (op == 2) printf("%d\n", tree_query(root, l, r)); else in(x),tree_change(root, l, r, x); } return 0;}
AC日记——Periodic RMQ Problem codeforces 803G
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。