首页 > 代码库 > 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