北京工程信息网站,中国互联网百强企业排名,图片外链在线生成,企业网站规划书HDU5737
题意 [1][1][1]有长度为nnn的序列A,BA,BA,B [2]Q[2]Q[2]Q此操作两种类型 (1,l,r,x)(1,l,r,x)(1,l,r,x)将区间[l,r][l,r][l,r]的aia_iai覆盖为xxx(2,l,r)(2,l,r)(2,l,r)询问区间[l,r][l,r][l,r]中有多少ai≥bia_i \ge b_iai≥bi
题解
考虑用线段树维护.
重点考…HDU5737
题意
[1][1][1]有长度为nnn的序列A,BA,BA,B [2]Q[2]Q[2]Q此操作两种类型
(1,l,r,x)(1,l,r,x)(1,l,r,x)将区间[l,r][l,r][l,r]的aia_iai覆盖为xxx(2,l,r)(2,l,r)(2,l,r)询问区间[l,r][l,r][l,r]中有多少ai≥bia_i \ge b_iai≥bi
题解
考虑用线段树维护.
重点考虑覆盖操作,当覆盖一个线段时,我们打上延迟修改标记(就是lazylazylazy标记).
但是当前线段的答案要立刻被计算出来,那么这里如何求呢?
其实就相当于找区间[l,r][l,r][l,r]中小于等于xxx的有多少个.
因此想到我们可以在线段树的每一个节点维护一个平衡树.
这样的话,空间复杂度是O(nlogn)O(nlogn)O(nlogn)
仅平衡树合并的时间复杂度就是O(nlogn2)O(nlogn^2)O(nlogn2),这个时间复杂度我们接受不了,因此我们要换一种能查询rankrankrank的数据结构,但是合并要快.
因此我们就想到了有序表,合并时候用归并排序即可,查找的时候使用lower_boundlower\_boundlower_bound即可.
空间复杂度是O(nlogn)O(nlogn)O(nlogn).
有序表合并的时间复杂度是O(nlogn)O(nlogn)O(nlogn),可以接受.
查询rankrankrank的时间复杂度为O(logn)O(logn)O(logn),而考虑如果修改时区间大小为n−1n-1n−1时,涉及到打lognlognlogn个覆盖标记,每打一个覆盖标记时候都要lognlognlogn时间复杂度来查rankrankrank,总的时间复杂度就是O(logn2)O(logn^2)O(logn2),那么询问的时间复杂度就是O(m∗logn∗logn)O(m*logn*logn)O(m∗logn∗logn),这是无法接受的.
因此我们考虑怎么优化这步操作.
如果我们能记录下来对于线段中的每个数xxx,在左线段中小于等于xxx的最大的位置和在右线段中小于等于xxx的最大位置,那么我们在changechangechange函数中,可以直接O(1)O(1)O(1)传递给儿子这个关键的位置.
这样总的时间复杂度就优化到了O(nlognmlogn)O(nlogn mlogn)O(nlognmlogn)
代码
#include iostream
#include algorithm
#include vector
#include cstring
#define pr(x) std::cout #x : x std::endl
#define rep(i,a,b) for(int i a;i b;i)
#define clr(x) memset(x,0,sizeof(x))
#define setinf(x) memset(x,0x3f,sizeof(x))const int N 100007;
const int P 1e97;struct node{int ans,tag,len;node(int ans 0,int tag -1,int len 1):ans(ans),tag(tag),len(len){}
}ns[N2],NIL;std::vectorint vec[N2],lft[N2],rgt[N2];int a[N],b[N];inline node maintain(node lch,node rch) {node res node(lch.ans rch.ans,-1,lch.len rch.len);return res;
}inline void tag(int o,int val){ns[o].ans val;ns[o].tag val;
}inline void pushdown(int o) {if(ns[o].tag ! -1) {if(ns[o].tag 0){tag(o1,0);tag(o1|1,0);}else {tag(o1,lft[o][ns[o].tag-1]);tag(o1|1,rgt[o][ns[o].tag-1]);}ns[o].tag -1;}
}inline void merge(int o){int posl 0,posr 0;while(posl vec[o1].size() || posr vec[o1|1].size()) {if(posl vec[o1].size()) vec[o].push_back(vec[o1|1][posr]);else if(posr vec[o1|1].size()) vec[o].push_back(vec[o1][posl]);else {if(vec[o1][posl] vec[o1|1][posr])vec[o].push_back(vec[o1][posl]);else vec[o].push_back(vec[o1|1][posr]);}}posl posr 0;rep(i,0,vec[o].size()-1) {while(posl vec[o1].size() vec[o1][posl] vec[o][i])posl;while(posr vec[o1|1].size() vec[o1|1][posr] vec[o][i])posr;lft[o].push_back(posl);rgt[o].push_back(posr);}
}inline void build(int o,int l,int r) {if(l r) {vec[o].push_back(b[l]);ns[o] node(a[l] b[l],-1,1);return ;}int mid (l r) 1;build(o1,l,mid);build(o1|1,mid1,r);ns[o] maintain(ns[o1],ns[o1|1]);merge(o);
}inline void change(int o,int l,int r,int cl,int cr,int val) {if(cl l r cr) {//val std::upper_bound(vec[o].begin(),vec[o].end(),val) - vec[o].begin();tag(o,val);return ;}if(r cl || cr l) return ;int mid (l r) 1;pushdown(o);change(o1,l,mid,cl,cr,val?lft[o][val-1]:0);change(o1|1,mid1,r,cl,cr,val?rgt[o][val-1]:0);ns[o] maintain(ns[o1],ns[o1|1]);
}inline node query(int o,int l,int r,int ql,int qr) {if(ql l r qr) return ns[o];if(r ql || qr l)return NIL;int mid (l r) 1;pushdown(o);node lch query(o1,l,mid,ql,qr);node rch query(o1|1,mid1,r,ql,qr);return maintain(lch,rch);
}
int T,n,m,A,B;int aa,bb,C,M,last;
inline int rnd(int last) {aa (36969 (last 3)) * (aa M) (aa 16);bb (18000 (last 3)) * (bb M) (bb 16);return (C ((aa 16) bb)) % 1000000000;
}inline void clear(int o,int l,int r){if(l r) {vec[o].clear(); lft[o].clear(); rgt[o].clear(); return ;}clear(o1,l,(lr)1);clear(o1|1,((lr)1)1,r);vec[o].clear();lft[o].clear();rgt[o].clear();
}
int main() {std::ios::sync_with_stdio(false);std::cin T;while(T--) {std::cin n m A B;long long ans 0;aa A,bb B,C ~(131), M (116)-1, last 0;rep(i,1,n) std::cin a[i];rep(i,1,n)std::cin b[i];build(1,1,n);rep(i,1,m) {int l (rnd(last) % n) 1,r (rnd(last) % n) 1,x rnd(last) 1;if(l r) std::swap(l,r);int tp (lrx)%2 0 ? 2:1;if(tp 1){x upper_bound(vec[1].begin(),vec[1].end(),x) - vec[1].begin();change(1,1,n,l,r,x);}else if(tp 2){node res query(1,1,n,l,r);ans ans 1LL * i * res.ans;last res.ans;}}std::cout ans % P std::endl;clear(1,1,n);}return 0;
}
