网站织梦程序改成wordpress,建立网站需要技术吗,淘宝客网站建设公司,国内免费的建网站平台[Luogu4198] 原题解 19.3.21 用线段树维护有关单调栈的问题 不要pushdown , 但是pushup的时候需要特别注意. 19.3.31 这里的\(pushup2\)其实就是几个特判 : 没有 , 直接返回当前区间答案 , 区间长度为\(1\) , 以及剩下两大类 , 这里有一个模板 : if(mx[ls]tmp) return push…[Luogu4198] 原题解 19.3.21 用线段树维护有关单调栈的问题 不要pushdown , 但是pushup的时候需要特别注意. 19.3.31 这里的\(pushup2\)其实就是几个特判 : 没有 , 直接返回当前区间答案 , 区间长度为\(1\) , 以及剩下两大类 , 这里有一个模板 : if(mx[ls]tmp) return pushup2(rs,mid1,r,tmp);
else return pushup2(ls,l,mid,tmp)len[rt]-len[ls]; 细节见代码 #includecstdio
#includealgorithm
using namespace std;
typedef lon7g long LL;
const int INF1e97;
inline LL read(){register LL x0,f1;register char cgetchar();while(c48||c57){if(c-)f-1;cgetchar();}while(c48c57)x(x3)(x1)(c15),cgetchar();return f*x;
}const int MAXN1e55;double a[MAXN];
int n,m;struct SGT{int len[MAXN2];double mx[MAXN2];
#define ls (rt1)
#define rs (rt1|1)inline void pushup1(int rt){mx[rt]max(mx[ls],mx[rs]);}inline int pushup2(int rt,int l,int r,double tmp){if(tmpmx[rt]) return 0;//这里必须有一个限制的变量 一个判没有if(a[l]tmp) return len[rt];//一个判最简单情况if(lr) return len[l]tmp;//分类讨论清楚:三种情况 不要忘了长度为1的特判int mid(lr)1;if(mx[ls]tmp) return pushup2(rs,mid1,r,tmp);//最后两大类else return pushup2(ls,l,mid,tmp)len[rt]-len[ls];//补上右边还能继续递增的,这个模板很重要}inline void modify(int rt,int l,int r,int x,int y){if(lrlx){mx[rt](double)y/x;//这里不要改a[rt]...len[rt]1;return;}int mid(lr)1;if(xmid) modify(ls,l,mid,x,y);else modify(rs,mid1,r,x,y);pushup1(rt);len[rt]len[ls]pushup2(rs,mid1,r,mx[ls]);//用左边的限定右边来更新右边,但不需要保存}
#undef ls
#undef rs
}T;int main(){nread(),mread();for(int i1;im;i){int xread(),yread();a[x](double)y/x;T.modify(1,1,n,x,y);printf(%d\n,T.len[1]);}
} 转载于:https://www.cnblogs.com/lizehon/p/10573945.html
