HDU5737

題意

$[1]$有長度為$n$的序列$A,B$
$[2]Q$此操作兩種類型

• $(1,l,r,x)$將區間$[l,r]$的$a_i$覆蓋為$x$
• $(2,l,r)$詢問區間$[l,r]$中有多少$a_i\ge b_i$

題解

考慮用線段樹維護.

重點考慮覆蓋操作,當覆蓋一個線段時,我們打上延遲修改標記(就是$lazy$標記).

但是當前線段的答案要立刻被計算出來,那么這里如何求呢?

其實就相當于找區間$[l,r]$中小于等于$x$的有多少個.

因此想到我們可以在線段樹的每一個節點維護一個平衡樹.

這樣的話,空間復雜度是$O(nlogn)$

僅平衡樹合并的時間復雜度就是$O(nlog{n}^2)$,這個時間復雜度我們接受不了,因此我們要換一種能查詢$rank$的數據結構,但是合并要快.

因此我們就想到了有序表,合并時候用歸并排序即可,查找的時候使用$lower\_bound$即可.

空間復雜度是$O(nlogn)$.

有序表合并的時間復雜度是$O(nlogn)$,可以接受.

查詢$rank$的時間復雜度為$O(logn)$,而考慮如果修改時區間大小為$n?1$時,涉及到打$logn$個覆蓋標記,每打一個覆蓋標記時候都要$logn$時間復雜度來查$rank$,總的時間復雜度就是$O(log{n}^2)$,那么詢問的時間復雜度就是$O(m?logn?logn)$,這是無法接受的.

因此我們考慮怎么優化這步操作.

如果我們能記錄下來對于線段中的每個數$x$,在左線段中小于等于$x$的最大的位置和在右線段中小于等于$x$的最大位置,那么我們在$change$函數中,可以直接$O(1)$傳遞給兒子這個關鍵的位置.

這樣總的時間復雜度就優化到了$O(nlogn+mlogn)$

代碼

#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 = 1e9+7;struct node{int ans,tag,len;node(int ans = 0,int tag = -1,int len = 1):ans(ans),tag(tag),len(len){} }ns[N<<2],NIL;std::vector<int> vec[N<<2],lft[N<<2],rgt[N<<2];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(o<<1,0);tag(o<<1|1,0);}else {tag(o<<1,lft[o][ns[o].tag-1]);tag(o<<1|1,rgt[o][ns[o].tag-1]);}ns[o].tag = -1;} }inline void merge(int o){int posl = 0,posr = 0;while(posl < vec[o<<1].size() || posr < vec[o<<1|1].size()) {if(posl == vec[o<<1].size()) vec[o].push_back(vec[o<<1|1][posr++]);else if(posr == vec[o<<1|1].size()) vec[o].push_back(vec[o<<1][posl++]);else {if(vec[o<<1][posl] < vec[o<<1|1][posr])vec[o].push_back(vec[o<<1][posl++]);else vec[o].push_back(vec[o<<1|1][posr++]);}}posl = posr = 0;rep(i,0,vec[o].size()-1) {while(posl < vec[o<<1].size() && vec[o<<1][posl] <= vec[o][i])posl++;while(posr < vec[o<<1|1].size() && vec[o<<1|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(o<<1,l,mid);build(o<<1|1,mid+1,r);ns[o] = maintain(ns[o<<1],ns[o<<1|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(o<<1,l,mid,cl,cr,val?lft[o][val-1]:0);change(o<<1|1,mid+1,r,cl,cr,val?rgt[o][val-1]:0);ns[o] = maintain(ns[o<<1],ns[o<<1|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(o<<1,l,mid,ql,qr);node rch = query(o<<1|1,mid+1,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(o<<1,l,(l+r)>>1);clear(o<<1|1,((l+r)>>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 = ~(1<<31), M = (1<<16)-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 = (l+r+x)%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; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的线段树-HDU5737-这题有点神的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。