本文主要是介绍Educational Codeforces Round 20 G. Periodic RMQ Problem（线段树+主席树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：http://codeforces.com/contest/803/problem/G
题解：
半夜三点闲来无事，激情刷题2333333
看到网上有dalao直接一颗线段树就搞定了。。。感觉自己白写了这么多啊？
其实考虑到整个序列是一个循环的，很容易想到会有很多的重复的状态，那么我们可以通过主席树来将所有的冗余状态合并起来进行维护。
更新操作可以拆分为，更新一整个周期的操作+更新周期的一部分的操作。对于更新一整个周期的操作，我们可以利用线段树区间更新最小值。对于局部的操作，可以直接在主席树上更新，然后将新的最小值插入到线段树上，注意，这类更新之前，我们要判断这个周期是否之前被操作过，相当于一个懒惰标记下放的过程。
查询的时候，也分为两种，覆盖一整个周期的+覆盖部分周期的，和更新类似，只要分类处理，下放懒惰标记就好了。。。
题目貌似不难，就是我写的太复杂了？还是菜啊。。。。
#include<bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
using namespace std;
const int MAXN=1e5+5;
const int M=MAXN*100;
const int SZ=1e4+5;
int n,q,tot,k,tot2;
int b[MAXN];
int T[MAXN/10],lson[M],rson[M],c[M],lazy[M],book[M],sv[M];
inline int getnode()
{int ret;if(tot2){ret=sv[tot2--];}else{ret=tot++;}book[ret]++;lazy[ret]=rson[ret]=lson[ret]=c[ret]=0;return ret;
}
inline void del(int now)
{if(now==0)return ;book[now]--;i这篇关于Educational Codeforces Round 20 G. Periodic RMQ Problem（线段树+主席树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
