- #include
- #include
- #include
- #include using namespace std;
- #definemaxn 100005struct TreeNodeType {
- int l, r, mid, min, flag;
- TreeNodeType *lc, *rc;
- TreeNodeType()
- {
- flag=0;
- lc = NULL;
- rc = NULL;
- }
- };
- structTreeNodeType *root, *rot;
- int n, k, m;
- inline void in(int&now)
- {
- charCget = getchar(); now =0;
- while(Cget >'9'|| Cget <'0') Cget = getchar();
- while(Cget >='0'&&Cget <='9')
- {
- now = now *10+ Cget -'0';
- Cget = getchar();
- }
- }
- voidtree_build_ori(TreeNodeType *&now,intl,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);
- }
- inttree_query_ori(TreeNodeType *&now,intl,int r)
- {
- if(now->l == l&&now->r == r)returnnow->min;
- if(l > now->mid)returntree_query_ori(now->rc, l, r);
- else if(r <= now->mid)returntree_query_ori(now->lc, l, r);
- else returnmin(tree_query_ori(now->lc, l, now->mid), tree_query_ori(now->rc, now->mid +1, r));
- }
- inline voidtree_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;
- }
- intsolve(intl,int r)
- {
- if(r-l+1>=n)returnrot->min;
- l%=n,r%=n;
- if(l==0) l=n;
- if(r==0) r=n;
- if(rreturnmin(tree_query_ori(rot, l, n), tree_query_ori(rot,1, r));
- else return tree_query_ori(rot,l,r);
- }
- voidtree_change(TreeNodeType *&now,intl,intr,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);
- }
- inttree_query(TreeNodeType *&now,intl,int r)
- {
- if(now->l == l&&now->r == r)returnnow->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)returntree_query(now->rc, l, r);
- else if(r <= now->mid)returntree_query(now->lc, l, r);
- else returnmin(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;
- }
来源: http://www.bubuko.com/infodetail-2050518.html