首页 > 代码库 > BZOJ 4262 线段树+期望
BZOJ 4262 线段树+期望
思路：
把询问离线下来，查询max和查询min相似，现在只考虑查询max
令sum[l,r,x]表示l到r内的数为左端点，x为右端点的区间询问的答案
那么询问就是sun[l1,r1,r2]-sum[l1,r1,l1-1]
从1到n枚举x，维护区间线段树表示sum[l,r,x]，发现从x-1转移到x的过程中，每个数加上了max(a[pos]..a[x])的答案。
用单调队列维护一个单调递减的序列，由于a数列是随机的，这个队列期望有log个元素，所以只需要对这log段暴力修改，复杂度nlog^2n
或者，只在元素进队和出队的时候做一些操作，写起来会复杂很多，但复杂度nlogn
From heheda
（其实先把所有的数求出来 做一遍 再取相反数 做一遍就好啦）
//By SiriusRen#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define int long longconst int N=200050,mod=1000000000;struct Node{ int id,l,r,pos,f;Node(){} Node(int I,int L,int R,int P,int F){id=I,l=L,r=R,pos=P,f=F;}}node[N];bool cmp(Node a,Node b){if(a.pos!=b.pos)return a.pos<b.pos;return a.f<b.f;}int n,t,l1,r1,l2,r2,stk[N],top,tree[N*16],lazy[N*16],ans[N],a[N],maxx;void insert(int l,int r,int pos,int L,int R,int wei){ if(l>=L&&r<=R){lazy[pos]+=wei;tree[pos]+=(r-l+1)*wei;return;} int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1; if(mid<L)insert(mid+1,r,rson,L,R,wei); else if(mid>=R)insert(l,mid,lson,L,R,wei); else insert(l,mid,lson,L,R,wei),insert(mid+1,r,rson,L,R,wei); tree[pos]=tree[lson]+tree[rson];}void push_down(int pos,int num){ int lson=pos<<1,rson=pos<<1|1; lazy[lson]+=lazy[pos],lazy[rson]+=lazy[pos]; tree[lson]+=lazy[pos]*(num-num/2),tree[rson]+=lazy[pos]*(num>>1); lazy[pos]=0;}int query(int l,int r,int pos,int L,int R){ if(l>=L&&r<=R)return tree[pos]; if(lazy[pos])push_down(pos,r-l+1); int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1; if(mid<L)return query(mid+1,r,rson,L,R); else if(mid>=R)return query(l,mid,lson,L,R); else return query(l,mid,lson,L,R)+query(mid+1,r,rson,L,R);}void solve(){ int now=1; for(int i=1;i<=maxx;i++){ while(node[now].pos==i&&node[now].f==-1)ans[node[now].id]-=query(1,maxx,1,node[now].l,node[now].r),now++; while(top&&a[stk[top]]<=a[i])top--; stk[++top]=i; for(int j=1;j<=top;j++)insert(1,maxx,1,stk[j-1]+1,stk[j],a[stk[j]]); while(node[now].pos==i)ans[node[now].id]+=query(1,maxx,1,node[now].l,node[now].r),now++; }}signed main(){ int fst=1023,sec=1025; for(int i=1;i<=100000;i++) a[i]=fst^sec,fst=fst*1023%mod,sec=sec*1025%mod; scanf("%lld",&t); for(int i=1;i<=t;i++){ scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2); node[++n]=Node(i,l1,r1,l2,-1); node[++n]=Node(i,l1,r1,r2,1); maxx=max(r1,max(maxx,r2)); } sort(node+1,node+1+n,cmp); solve(); memset(tree,0,sizeof(tree)),memset(lazy,0,sizeof(lazy)); for(int i=1;i<=100000;i++)a[i]=-a[i]; solve(); for(int i=1;i<=t;i++)printf("%lld\n",ans[i]);}
BZOJ 4262 线段树+期望
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。