i题意
和poj1823差不多,加了一个查询最左可行的位置
思路
查询的时候根据不同的sta,分情况讨论
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int nMax = 1000000; struct{ int l,r,val,lmx,rmx,sta; //0empty 1full -1mix }node[3*nMax]; void gao(int u){ if(node[u].sta == 0){ node[u].val = node[u].lmx = node[u].rmx = node[u].r - node[u].l + 1; }else{ node[u].val = node[u].lmx = node[u].rmx =0; } } void build(int l ,int r ,int u){ node[u].l = l; node[u].r = r; node[u].sta = 0; gao(u); if(l == r){ return; } int m = (l+r)>>1; build(l ,m ,u*2); build(m+1 ,r ,u*2 + 1); } void update(int left ,int right ,int ope ,int u){ int l = node[u].l; int r = node[u].r; if(l == left && r == right){ node[u].sta = ope; gao(u); return; } if(node[u].sta == ope)return ; if(node[u].sta != -1){ node[2*u].sta = node[2*u+1].sta = node[u].sta; gao(u*2),gao(u*2+1); node[u].sta = -1; } int m = (l + r)>>1; if(right <= m){ update(left ,right ,ope ,u*2); }else{ if(left >= m + 1){ update(left ,right ,ope ,u*2+1); }else{ update(left ,m ,ope ,u*2); update(m+1,right ,ope ,u*2+1); } } if(node[u*2].sta == 0){ node[u].lmx = node[u*2].val + node[u*2+1].lmx; }else{ node[u].lmx = node[u*2].lmx; } if(node[u*2+1].sta == 0){ node[u].rmx = node[u*2+1].val + node[u*2].rmx; }else{ node[u].rmx = node[u*2+1].rmx; } node[u].val = max(node[u*2].val,node[u*2+1].val); node[u].val = max(node[u].val,node[u*2].rmx+node[u*2+1].lmx); if(node[u*2].sta == node[u*2+1].sta){ node[u].sta = node[u*2].sta; } } int query(int val ,int u){ if(node[u].sta == 0 && node[u].val >= val){ return node[u].l; } if(node[u].sta == 1){ return 0; } if(node[u].sta == -1){ if(node[u*2].val >= val){ return query(val ,2*u); }else{ if(node[2*u].rmx + node[2*u+1].lmx >= val){ return node[2*u].r - node[2*u].rmx + 1; }else{ return query(val ,u*2 + 1); } } } return 0; } int main(){ int n ,m ,a ,b ,c; while(scanf("%d%d",&n,&m)!=EOF){ build(1 ,n ,1); while(m--){ scanf("%d",&a); if(a == 1){ scanf("%d",&b); c = query(b ,1); printf("%d\n",c); if(c != 0){ update(c ,c+b-1 ,1 ,1); } }else{ scanf("%d%d",&b,&c); update(b ,b + c -1 ,0 ,1 ); } } } return 0; }
相关推荐
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
NULL 博文链接:https://128kj.iteye.com/blog/1740501
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1739733
线段树、树状数组算法入门 加 poj解题报告 pdf文档
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
poj 2763 程序 线段树 LCA 2000MS AC
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ题解 个人写法 线段树每个人都不一样
NULL 博文链接:https://128kj.iteye.com/blog/1746750
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
NULL 博文链接:https://128kj.iteye.com/blog/1733777
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论