AC日记——Periodic RMQ Problem codeforces 803G

G - Periodic RMQ Problem

思路：

　　题目给一段序列，然后序列复制很多次；

　　维护序列很多次后的性质；

　　线段树动态开点；

来，上代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 100005

struct TreeNodeType {

    int l, r, mid, min, flag;

    TreeNodeType *lc, *rc;

    TreeNodeType()

    {

        flag=;

        lc = NULL;

        rc = NULL;

    }

};

struct TreeNodeType *root, *rot;

int n, k, m;

inline void in(int &now)

{

    char Cget = getchar(); now = ;

    while (Cget > '' || Cget < '') Cget = getchar();

    while (Cget >= ''&&Cget <= '')

    {

        now = now *  + Cget - '';

        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) >> ;

    }

    if (l == r)

    {

        in(now->min);

        return;

    }

    tree_build_ori(now->lc, l, now->mid);

    tree_build_ori(now->rc, now->mid + , 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 + , 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 = ;

}

int solve(int l, int r)

{

    if(r-l+>=n) return rot->min;

    l%=n,r%=n;

    if(l==) l=n;

    if(r==) r=n;

    if(r<l) return min(tree_query_ori(rot, l, n), tree_query_ori(rot, , 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 + ;

        now->rc->r = now->r;

        now->rc->mid = (now->rc->r + now->rc->l) >> ;

        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) >> ;

        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 + , 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 + ;

        now->rc->r = now->r;

        now->rc->mid = (now->rc->r + now->rc->l) >> ;

        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) >> ;

        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 + , 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, , n), in(m);

    root = new TreeNodeType;

    root->l = , root->r = n*k, root->mid =  + n*k >> , root->min = rot->min;

    for (; m--;)

    {

        in(op), in(l), in(r);

        if (op == ) printf("%d\n", tree_query(root, l, r));

        else in(x),tree_change(root, l, r, x);

    }

    return ;

}