題目鏈接

https://codeforces.com/contest/1004/problem/F

題解

這種水題都不會做了怎么。。
考慮一個序列的前綴 \(\text{or}\) 值只會變化 \(O(\log W)\) 次，于是線段樹維護每個區間的前綴和后綴 \(\text{or}\) 值即可。
時間復雜度 \(O(n\log n\log W)\).

代碼

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define iter iterator #define riter reversed_iterator #define y1 Lorem_ipsum_dolor #define pii pair<int,int> using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int mxN = 1e5; const int lgA = 20; int a[mxN+3]; int n,q,X;struct Data {pii pre[lgA+3],suf[lgA+3]; llong sum; int pren,sufn; } sgt[mxN*4+3]; Data operator +(Data ls,Data rs) {Data ret; ret.sum = ls.sum+rs.sum; ret.pren = ret.sufn = 0;llong cur = 0ll;for(int i=1,j=rs.pren+1; i<=ls.sufn; i++){while(j>1&&(rs.pre[j-1].first|ls.suf[i].first)>=X) {j--; cur += rs.pre[j].second;}ret.sum += 1ll*ls.suf[i].second*cur;}for(int i=1; i<ls.pren; i++) {ret.pre[++ret.pren] = ls.pre[i];}pii tmp = ls.pre[ls.pren];for(int i=1; i<=rs.pren; i++){if((tmp.first|rs.pre[i].first)==tmp.first) {tmp.second += rs.pre[i].second;}else{ret.pre[++ret.pren] = tmp;tmp.first |= rs.pre[i].first; tmp.second = rs.pre[i].second;}}ret.pre[++ret.pren] = tmp;for(int i=1; i<rs.sufn; i++) {ret.suf[++ret.sufn] = rs.suf[i];}tmp = rs.suf[rs.sufn];for(int i=1; i<=ls.sufn; i++){if((tmp.first|ls.suf[i].first)==tmp.first) {tmp.second += ls.suf[i].second;}else{ret.suf[++ret.sufn] = tmp;tmp.first |= ls.suf[i].first; tmp.second = ls.suf[i].second;}}ret.suf[++ret.sufn] = tmp;return ret; } void build(int u,int le,int ri) {if(le==ri) {sgt[u].pren = sgt[u].sufn = 1,sgt[u].pre[1] = sgt[u].suf[1] = mkpr(a[le],1),sgt[u].sum = a[le]>=X?1:0; return;}int mid = (le+ri)>>1;build(u<<1,le,mid); build(u<<1|1,mid+1,ri);sgt[u] = sgt[u<<1]+sgt[u<<1|1]; } void modify(int u,int le,int ri,int pos,int x) {if(le==ri) {sgt[u].pre[1] = sgt[u].suf[1] = mkpr(x,1),sgt[u].sum = x>=X?1:0; return;}int mid = (le+ri)>>1;if(pos<=mid) modify(u<<1,le,mid,pos,x); else modify(u<<1|1,mid+1,ri,pos,x);sgt[u] = sgt[u<<1]+sgt[u<<1|1]; } Data query(int u,int le,int ri,int lb,int rb) {if(le>=lb&&ri<=rb) {return sgt[u];}int mid = (le+ri)>>1;if(rb<=mid) {return query(u<<1,le,mid,lb,rb);}else if(lb>mid) {return query(u<<1|1,mid+1,ri,lb,rb);}else {return query(u<<1,le,mid,lb,mid)+query(u<<1|1,mid+1,ri,mid+1,rb);} }int main() {n = read(),q = read(),X = read();for(int i=1; i<=n; i++) a[i] = read();build(1,1,n);while(q--){int opt = read();if(opt==1){int u = read(),x = read();modify(1,1,n,u,x);}else{int l = read(),r = read();Data ans = query(1,1,n,l,r);printf("%I64d\n",ans.sum);}}return 0; }

總結

以上是生活随笔為你收集整理的Codeforces 1004F Sonya and Bitwise OR (线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

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