AcWing提高算法課Level-3 第四章 高級數據結構

AcWing提高算法課Level-3 第四章 高級數據結構

并查集
AcWing 1250. 格子游戲1167人打卡
AcWing 1252. 搭配購買1064人打卡
AcWing 237. 程序自動分析940人打卡
AcWing 239. 奇偶游戲629人打卡
AcWing 238. 銀河英雄傳說844人打卡

樹狀數組
AcWing 241. 樓蘭圖騰1083人打卡
AcWing 242. 一個簡單的整數問題1050人打卡
AcWing 243. 一個簡單的整數問題2916人打卡
AcWing 244. 謎一樣的牛869人打卡

線段樹
AcWing 1275. 最大數1125人打卡
AcWing 245. 你能回答這些問題嗎955人打卡
AcWing 246. 區間最大公約數762人打卡
AcWing 243. 一個簡單的整數問題2845人打卡
AcWing 247. 亞特蘭蒂斯482人打卡
AcWing 1277. 維護序列638人打卡

可持久化數據結構
AcWing 256. 最大異或和388人打卡
AcWing 255. 第K小數428人打卡

平衡樹
AcWing 253. 普通平衡樹415人打卡
AcWing 265. 營業額統計344人打卡

AC自動機
AcWing 1282. 搜索關鍵詞441人打卡
AcWing 1285. 單詞297人打卡

代碼

AcWing 1250. 格子游戲1167人打卡

//題意：給出n*n的網格，按順序m次操作，每次從(x,y)向右或下連畫一條邊，求第幾次時能圍成封閉的圖形。
//思路：把n*n個坐標看成對應的點（可以用x*n+y映射），問題轉換為每次連一條邊，求最早何時形成環。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 210;int fa[maxn*maxn+10];
void init(int n){for(int i = 1; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}int getid(int x, int y){return x*maxn+y;
}int main(){ios::sync_with_stdio(false);int n, m;   cin>>n>>m;init(maxn*maxn);for(int i = 1; i <= m; i++){int x, y;  char op;cin>>x>>y>>op;int a = getid(x,y), b = getid(x+(op=='D'), y+(op=='R'));int aa=find(a), bb=find(b);if(aa==bb){cout<<i<<"\n";return 0;}else{merge(aa,bb);}}cout<<"draw\n";return 0;
}

AcWing 1252. 搭配購買1064人打卡

//題意：n朵云，每朵有價錢和價值。m個關系，買了u就必須買v。一共有w錢，最大化價值。
//思路：m個關系并查集處理后，得到若干個獨立的連通塊，把這些塊作為物品，計算出價錢和價值，跑01背包即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;int c[maxn], d[maxn];
int dp[maxn];int fa[maxn+10];
void init(int n){for(int i = 1; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}int main(){ios::sync_with_stdio(false);//UnionFindSetint n, m, w;  cin>>n>>m>>w;for(int i = 1; i <= n; i++)cin>>c[i]>>d[i];//價錢,價值init(n);for(int i = 1; i <= m; i++){int u, v;  cin>>u>>v;  merge(u,v);}map<int,int>cc, dd;for(int i = 1; i <= n; i++){cc[find(i)] += c[i];dd[find(i)] += d[i];}vector<pair<int,int> >vc(cc.begin(),cc.end()), vd(dd.begin(),dd.end());//01 Packfor(int i = 0; i < vc.size(); i++){for(int j = w; j >= vc[i].second; j--){dp[j] = max(dp[j], dp[j-vc[i].second]+vd[i].second);}}cout<<dp[w]<<"\n";return 0;
}

AcWing 237. 程序自動分析940人打卡

//題意：n個條件，每個條件(xi,xj,e)表示xi==xj或xi!=xj，判斷是否有沖突。
//思路：先并查集合并所有xi==xj的數到相同集合，然后跑xi!=xj的判斷沖突。因為數字比較大所以先離散化一下。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;vector<pair<int,int> >eq, uneq;//離散化
unordered_map<int,int>ma; int cnt = 0;
int mp(int x){if(!ma.count(x))ma[x]=++cnt;return ma[x];
}//并查集
int fa[maxn+10];
void init(int n){ for(int i = 1; i <= n; i++)fa[i]=i; }
int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}int main(){ios::sync_with_stdio(false);int T;  cin>>T;while(T--){eq.clear(), uneq.clear();cnt = 0;  ma.clear();int n;  cin>>n;for(int i = 1; i <= n; i++){int x, y, e;  cin>>x>>y>>e;x = mp(x), y = mp(y);if(e==1){eq.push_back({x,y});}else{uneq.push_back({x,y});}}init(cnt);for(auto x : eq)merge(x.first, x.second);int ok = 1;for(auto x : uneq){if(find(x.first)==find(x.second)){ok = 0; break;}}if(ok==0)cout<<"NO\n";else cout<<"YES\n";}return 0;
}

AcWing 239. 奇偶游戲629人打卡

//題意：有一個長為n的01序列（未給出），按順序給出m次詢問的答案，每次回答區間[l,r]中1的個數是奇數還是偶數，求從第幾個詢問開始沖突。
/*思路：
+ 用s[i]表示原序列的前綴和，那么就可以得到區間[l,r]中1的個數(即s[r]-s[l-1])的奇偶性。
+ 當s[r]-s[l-1]為奇數時，可以推出，s[r]與s[l-1]肯定是一個奇數一個偶數。反之兩個肯定都為奇數或者偶數。
+ 用擴展域維護關系的傳遞性，將每個節點x拆為奇數域與偶數域，分別表示x是奇數和x是偶數，維護合并的時候判斷沖突信息即可。
+ 節點范圍1e9較大，需要離散化一下。
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;//離散化
unordered_map<int,int>ma; int cnt = 0;
int mp(int x){if(!ma.count(x))ma[x]=++cnt;return ma[x];
}//并查集
int fa[2*maxn+10];
void init(int n){ for(int i = 1; i <= n; i++)fa[i]=i; }
int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}int main(){ios::sync_with_stdio(false);int n;  cin>>n;int m;  cin>>m;init(2*maxn);int ans = m; //無矛盾時答案即為問題的數量for(int i = 1; i <= m; i++){int l, r; string op;  cin>>l>>r>>op;l = mp(l-1), r = mp(r);   //sum[l~r]=s[r]-s[l-1];if(op=="even"){           //sum[l~r]為偶數，即s[l-1]和s[r]奇偶性相同if(find(l+maxn) == find(r)){ //沖突了ans = i-1; break;}merge(l,r);          //s[l]和s[r]都是奇數merge(l+maxn,r+maxn);//或者s[l]和s[r]都是偶數}else{if(find(l)==find(r)){ans = i-1; break;}merge(l+maxn, r);merge(l,r+maxn);}}cout<<ans<<"\n";return 0;
}

AcWing 238. 銀河英雄傳說844人打卡

//帶權并查集
//維護每個節點(戰艦)到該列艦首的位置和每列戰艦的長度
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
typedef long long LL;int fa[maxn+10];
int sz[maxn], rk[maxn];
void init(int n){for(int i = 1; i <= n; i++)fa[i]=i,sz[i]=1;}
int find(int x){if(fa[x]==x)return x;else{int t = find(fa[x]);rk[x] += rk[fa[x]];return fa[x]=t;}
}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y){fa[x]=y;rk[x] += sz[y];sz[y] += sz[x];sz[x] = 0;}
}int main(){ios::sync_with_stdio(false);int n = 30000;init(n);int T;  cin>>T;while(T--){char op; int a, b;cin>>op>>a>>b;if(op=='M'){merge(a,b);//a整列接到b后面}else{if(find(a)!=find(b)){cout<<"-1\n";}else{cout<<abs(rk[a]-rk[b])-1<<"\n";}}}return 0;
}

AcWing 241. 樓蘭圖騰1083人打卡

//題意：給出一條橫軸上的n個點的縱坐標，求有多少個v和∧圖形（中間點y值高于兩邊或低于兩邊）
//思路：從左向右依次遍歷每個數a[i]，使用樹狀數組統計在i位置之前所有比a[i]大的數的個數、以及比a[i]小的數的個數。統計完成后，將a[i]加入到樹狀數組。
//思路：再從右向左依次遍歷每個數a[i]，使用樹狀數組統計在i位置之后所有比a[i]大的數的個數、以及比a[i]小的數的個數。統計完成后，將a[i]加入到樹狀數組。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2000010;int a[maxn];
int sm[maxn], bg[maxn];//左邊比a[i]小，比a[i]大的數的個數//樹狀數組
int n, b[maxn];
void add(int x, int v){ for(int i = x; i <= n; i+=i&(-i))b[i]+=v;}//序列中第x個數加上k
int query(int x){ int ans=0;for(int i=x;i>0;i-=i&(-i))ans+=b[i];return ans;}//查詢序列前x個數的和int main(){ios::sync_with_stdio(false);cin>>n;for(int i = 1; i <= n; i++)cin>>a[i];for(int i = 1; i <= n; i++){//從左往右，暫存數據int y = a[i];sm[i] = query(y-1); //位置i前的數中，數字[1,y-1]的出現次數bg[i] = (i-1)-query(y);//總個數-小于等于a[i]的數的個數add(y,1);}memset(b,0,sizeof(b));LL ansv = 0, ansa = 0;for(int i = n; i >= 1; i--){//從右往左，更新答案int y = a[i];ansa += (LL)sm[i]*(query(y-1)); //右邊比a[i]小的ansv += (LL)bg[i]*(query(n)-query(y));//右邊比a[i]大的add(y,1);}cout<<ansv<<" "<<ansa<<"\n";return 0;
}

AcWing 242. 一個簡單的整數問題1050人打卡

//題意：維護一個序列，支持區間加值和單點詢問
//思路：樹狀數組維護差分序列，查詢操作等價于對差分做前綴和，即單點的值。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2000010;//樹狀數組
int n, b[maxn];
void add(int x, int v){ for(int i = x; i <= n; i+=i&(-i))b[i]+=v;}//序列中第x個數加上k
int query(int x){ int ans=0;for(int i=x;i>0;i-=i&(-i))ans+=b[i];return ans;}//查詢序列前x個數的和int main(){ios::sync_with_stdio(false);int q;  cin>>n>>q;for(int i = 1; i <= n; i++){int x;  cin>>x;add(i,x);  add(i+1,-x);//維護差分}while(q--){string op;  cin>>op;if(op=="Q"){int x;  cin>>x;cout<<query(x)<<"\n";//跑前綴和==單點查詢}else{int l, r, x;  cin>>l>>r>>x;add(l,x); add(r+1,-x);//維護差分}}return 0;
}

AcWing 243. 一個簡單的整數問題2916人打卡

//題意：維護一個序列，支持區間加值和區間詢問
//思路：考慮上一題的區間加值，方法是維護差分數列，查詢時sum{b1+b2+..bx}即為a[x]的值。
//思路：此時如果繼續暴力區間查詢的話，就是再套一層循環算出a1~ax的值，加起來時可以發現，對于[1,r]的查詢，原式的值為ans=(r-1+1)b1+(r-2+1)b2+...+(r-r+1)br，即可以化簡為(r-i+1)*bi，可以提取i*bi，單獨再開一個樹狀數組維護一下。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;//樹狀數組, 維護差分b[i]
LL n, b[maxn];
void add(int x, LL v){ for(int i = x; i <= n; i+=i&(-i))b[i]+=v;}//序列中第x個數加上k
LL query(int x){ LL ans=0;for(int i=x;i>0;i-=i&(-i))ans+=b[i];return ans;}//查詢序列前x個數的和
//樹狀數組, 維護i*b[i]
LL b2[maxn];
void add2(int x, LL v){ for(int i = x; i <= n; i+=i&(-i))b2[i]+=v;}//序列中第x個數加上k
LL query2(int x){ LL ans=0;for(int i=x;i>0;i-=i&(-i))ans+=b2[i];return ans;}//查詢序列前x個數的和//題目
LL a[maxn];
LL calc(int x){ return query(x)*(x+1)-query2(x); }int main(){ios::sync_with_stdio(false);int q;  cin>>n>>q;for(int i = 1; i <= n; i++){cin>>a[i];LL x = a[i]-a[i-1]; //插入原始的差分值add(i,x);  add2(i,x*i); }while(q--){string op;  cin>>op;if(op=="Q"){int l, r;  cin>>l>>r;cout<<calc(r)-calc(l-1)<<"\n";}else{int l, r, x;  cin>>l>>r>>x;add(l,x); add(r+1,-x);  //維護差分進行區間修改add2(l,l*x); add2(r+1,-(r+1)*x);}}return 0;
}

AcWing 244. 謎一樣的牛869人打卡

//題意：1-n的數字隨機排列，給出每個數字前比它小的數字個數，求原先的排列。
//思路：考慮最后一個數字，如果前面有x個比他小，那么他就是x+1。然后對于倒數第i個數字，就是那些已經知道數值的數字后，第n-1小的數+1。
//思路：新建全為1的數列代表所有位置的高度都未知，用樹狀數組維護前綴和，如果某位置前綴和==a[i]+1（即前面到此位置有a[i]個不知道大小的數，這個位置可以二分），那么該下標就是第i個位置的數，將此位置改為0。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;int a[maxn], ans[maxn];//樹狀數組
int n, b[maxn];
void add(int x, int v){ for(int i = x; i <= n; i+=i&(-i))b[i]+=v;}//序列中第x個數加上k
int query(int x){ int ans=0;for(int i=x;i>0;i-=i&(-i))ans+=b[i];return ans;}//查詢序列前x個數的和int main(){ios::sync_with_stdio(false);cin>>n;for(int i = 2; i <= n; i++)cin>>a[i];for(int i = 1; i <= n; i++)add(i,1);for(int i = n; i >= 1; i--){int l = 1, r = n;while(l < r){int mid = (l+r)>>1;if(query(mid)<a[i]+1)l = mid+1;else r = mid;}ans[i] = l;add(l,-1);}for(int i = 1; i <= n; i++)cout<<ans[i]<<"\n";return 0;
}

AcWing 1275. 最大數1125人打卡

//題意：維護一個空序列，m次操作，每次可以末尾添加一個數或詢問后L個數的最大值。
//思路：最大值rmq可以線段樹維護，對于不定長的n，可以建一顆m的樹，然后維護當前長度n，每次修改位置n的值即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5+10;//線段樹
#define lch p<<1
#define rch p<<1|1
struct node{int l, r, v;}tr[maxn<<2];
void build(int p, int l, int r){tr[p] = {l, r, 0};if(l==r)return ;int mid = l+r>>1;build(lch, l, mid);build(rch, mid+1, r);
}
void update(int p, int x, int v){//修改位置x（即長為n的末尾）的值為v, 即單點修改if(tr[p].l==tr[p].r)tr[p].v=v;else{int mid = tr[p].l+tr[p].r>>1;if(x<=mid)update(lch, x, v);else update(rch, x, v);tr[p].v = max(tr[lch].v, tr[rch].v);//回溯}
}
int query(int p, int l, int r){ //查詢[n-L+1, n]內的最大值if(tr[p].l>=l&&tr[p].r<=r)return tr[p].v;int mid = tr[p].l+tr[p].r>>1, res = 0;if(l<=mid)res = query(lch,l,r);if(r >mid)res = max(res, query(rch,l,r));return res;
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n=0, last=0; //當前長度n，上一次的值lastint m, mod;  cin>>m>>mod;build(1,1,m);while(m--){char op;  cin>>op;if(op=='A'){int x;  cin>>x;update(1, ++n,((LL)x+last)%mod);//WA}else{int L;  cin>>L;cout<<(last = query(1,n-L+1,n))<<"\n";}}return 0;
}

AcWing 245. 你能回答這些問題嗎955人打卡

//題意：維護一個序列，支持單點修改和求區間最大子段和
//思路：
//+ 最大子段和的遞歸分治求法（將序列劃分為左右兩部分，則最大子段和可能在三處出現：左半部、右半部以及跨越左右邊界的部分，l==r時為遞歸邊界）
//+ 線段樹維護：區間左右端點起以及整個區間的最大子段和，轉移時候=max{左右兒子的mx，跨越左右兒子中點的子段和}
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5e5+10;//線段樹
struct Segment_Tree{struct node{LL ml, mr, mx, sum; //分別維護左右端點和區間的mx，以及區間sumvoid operator = (LL k){sum=ml=mr=mx=k;}node(){sum=ml=mr=mx=0;}}tr[maxn<<2|1];#define lch p<<1#define rch p<<1|1node pushup(node l, node r){node t;t.sum = l.sum + r.sum;t.ml = max(l.ml, l.sum+r.ml);t.mr = max(r.mr, r.sum+l.mr);t.mx = max(l.mr+r.ml,max(l.mx, r.mx));return t;}void build(LL p, LL l, LL r){if(l==r){int x; cin>>x; tr[p]=x;}else{LL mid = l+r>>1;build(lch, l, mid);build(rch, mid+1, r);tr[p] = pushup(tr[lch], tr[rch]);}}void update(LL p, LL l, LL r, LL x, LL k){if(l==r){if(l==x)tr[p] = k;return ;}LL mid = l+r>>1;if(x<=mid)update(lch, l, mid, x, k);if(x> mid)update(rch, mid+1, r, x, k);tr[p] = pushup(tr[lch], tr[rch]);}node query(LL p, LL l, LL r, LL ql, LL qr){if(ql<=l && r<=qr)return tr[p];LL mid = l+r>>1;if(qr<=mid)return query(lch, l, mid, ql, qr);if(ql > mid)return query(rch, mid+1, r, ql, qr);return pushup(query(lch, l, mid, ql, qr), query(rch, mid+1, r, ql, qr));}
}sgt;int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n, m;  cin>>n>>m;sgt.build(1,1,n);while(m--){int op;  cin>>op;if(op==1){int l, r;  cin>>l>>r;if(l>r)swap(l,r);cout<<sgt.query(1,1,n,l,r).mx<<"\n";}else{int x, v;  cin>>x>>v;sgt.update(1,1,n, x,v);}}return 0;
}

AcWing 246. 區間最大公約數762人打卡

//題意：維護一個序列，支持區間修改和求區間GCD
//思路：
//+ 對于修改，由gcd(a,b)=gcd(a,a-b)得gcd(a1,a2,..,an)=gcd(a1,a2-a1,a3-a2,..an-a_n-1)，可以線段樹維護原序列差分的gcd，區間修改即轉換為單點修改。
//+ 對于查詢，因為差分已經被修改了，所以最開始額外開一個樹狀數組維護差分，先查詢前綴和后得到當前a[l]的值，再與區間[l+1,r]的gcd求公約數即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5e5+10;
LL gcd(LL a, LL b){ return !b?a:gcd(b,a%b); }LL n, m;
LL a[maxn], d[maxn];//差分//樹狀數組
LL b[maxn];
void add(LL x, LL v){ for(LL i = x; i <= n; i+=i&(-i))b[i]+=v;}
LL ask(LL x){ LL ans=0;for(LL i=x;i>0;i-=i&(-i))ans+=b[i];return ans;}//線段樹
#define lch p<<1
#define rch p<<1|1
struct node{LL l, r, val;}tr[maxn<<2];
void build(LL p, LL l, LL r){tr[p].l = l, tr[p].r = r;if(l==r){tr[p].val = d[l]; return ;}LL mid = l+r>>1;build(lch, l, mid);build(rch, mid+1, r);tr[p].val = gcd(tr[lch].val, tr[rch].val);
}
void change(LL p, LL x, LL v){if(tr[p].l == tr[p].r){tr[p].val += v; return ;}LL mid = tr[p].l+tr[p].r>>1;if(x <= mid)change(lch, x, v);else change(rch, x, v);tr[p].val = gcd(tr[lch].val, tr[rch].val);
}
LL query(LL p, LL ql, LL qr){if(ql<=tr[p].l && qr>=tr[p].r)return tr[p].val;LL mid = tr[p].l+tr[p].r>>1, res = 0;if(ql <= mid)res = gcd(res, query(lch, ql, qr));if(qr > mid) res = gcd(res, query(rch, ql, qr));return abs(res);//防止負數
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n>>m;for(int i = 1; i <= n; i++){cin>>a[i];  d[i]=a[i]-a[i-1];}build(1,1,n);while(m--){string op;  cin>>op;if(op=="Q"){LL l, r;  cin>>l>>r;cout<<gcd(a[l]+ask(l), query(1,l+1,r) )<<"\n";}else{LL l, r, val;  cin>>l>>r>>val;add(l, val);  add(r+1,-val);change(1,l,val); if(r<n)change(1,r+1,-val);//防止n+1越界}}return 0;
}

AcWing 243. 一個簡單的整數問題2 845人打卡

//題意：維護一個序列，支持區間加值和區間詢問
//思路：線段樹打lazy tag即可
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;LL n, q, a[maxn];//線段樹
#define lch p<<1
#define rch p<<1|1
struct node{int l, r; LL sum, tag;}tr[maxn<<2];
void build(int p, int l, int r){tr[p].l=l, tr[p].r = r;if(l==r){tr[p].sum = a[l];  tr[p].tag = 0;return ;}int mid = l+r>>1;build(lch, l, mid);build(rch, mid+1, r);tr[p].sum = tr[lch].sum + tr[rch].sum;
}
LL query(int p, int ql, int qr){if(ql<=tr[p].l && tr[p].r<=qr)return tr[p].sum;int mid = tr[p].l+tr[p].r>>1;LL res = tr[p].tag*(min(tr[p].r, qr)- max(tr[p].l, ql)+1);//pushdown_計算懶標記的影響if(ql <= mid)res += query(lch, ql, qr);if(qr >= mid+1)res += query(rch, ql, qr);return res;
}
void change(int p, int cl, int cr, int cd){if(cl<=tr[p].l && tr[p].r <= cr){tr[p].sum += cd*(tr[p].r-tr[p].l+1);tr[p].tag += cd;return ;}int mid = tr[p].l+tr[p].r>>1;if(cl <= mid)change(lch, cl, cr, cd);if(cr >= mid+1)change(rch, cl, cr,cd);tr[p].sum = tr[lch].sum + tr[rch].sum+tr[p].tag*(tr[p].r-tr[p].l+1); //pushup_懶標記也算上
}int main(){ios::sync_with_stdio(false);cin>>n>>q;for(int i = 1; i <= n; i++)cin>>a[i];build(1,1,n);while(q--){string op;  cin>>op;if(op=="Q"){int l, r;  cin>>l>>r;cout<<query(1,l,r)<<"\n";}else{int l, r, x;  cin>>l>>r>>x;change(1,l,r,x);}}return 0;
}

AcWing 247. 亞特蘭蒂斯482人打卡

//題意：給出平面中的n個長方形，求總面積.
//思路：掃描線求矩形面積并板子
#include<bits/stdc++.h>
typedef double LL;
using namespace std;
const int maxn = 1e5+10;//掃描線: 維護線段端點X和線段信息line[l,r,h,(1/-1)]
LL X[maxn<<1];
struct Scan{ LL l, r, h; int mark; }line[maxn<<2];
bool operator < (Scan a,Scan b){return a.h<b.h;}//線段樹: sum維護被覆蓋次數, len維護區間被截長度
#define lch (p<<1)
#define rch (p<<1|1)
struct Sgt{ int l, r, sum; LL len; }tree[maxn<<2];
void build(int p, int l, int r){tree[p] = Sgt{l,r,0,0};if(l==r)return ;int mid = l+r>>1;build(lch, l, mid);build(rch, mid+1, r);return ;
}
void push_up(int p){int l = tree[p].l, r = tree[p].r;if(tree[p].sum!=0){ //被覆蓋tree[p].len = X[r+1]-X[l];//更新長度,將線段樹節點x的[l,r]與實際區間[X[l],X[r+1]]對應，保證了葉節點不是一個端點}else{tree[p].len = tree[lch].len+tree[rch].len;//合并兒子信息}
}
void update(int p, LL L, LL R, int c){int l = tree[p].l, r = tree[p].r;if(X[r+1]<=L || R<=X[l])return ;//考慮[2,5],[5,8]兩條線段, 要修改[1,5]區間的sum//雖然5在這個區間內，[5,8] 卻并不是我們希望修改的線段if(L <= X[l] && X[r+1]<=R){tree[p].sum += c;push_up(p);return ;}update(lch,L,R,c);update(rch,L,R,c);push_up(p);
}int main(){//ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n, cnt=0;while(cin>>n &&n){memset(tree,0,sizeof(tree));cout<<"Test case #"<<++cnt<<"\n";for(int i = 1; i <= n; i++){LL x1, y1, x2, y2;cin>>x1>>y1>>x2>>y2;X[2*i-1]=x1, X[2*i]=x2;line[2*i-1] = Scan{x1,x2,y1,1};line[2*i] = Scan{x1,x2,y2,-1};}n <<= 1;  //一共有2*n條線段sort(line+1, line+n+1);sort(X+1, X+n+1);       //端點排序int tot = unique(X+1,X+n+1)-X-1; //端點去重離散化,建立端點[l,r]與[1,n]的對應關系build(1,1,tot-1);      //用線段端點[X[1], X[tot]]建線段樹LL ans = 0;for(int i = 1; i < n; i++){//最后一條邊不用update(1,line[i].l,line[i].r, line[i].mark);//掃描信息ans += tree[1].len*(line[i+1].h-line[i].h);//統計面積}//cout<<ans<<"\n";printf("Total explored area: %.2lf\n\n",ans);}return 0;
}

AcWing 1277. 維護序列638人打卡

//題意：維護一個序列，支持區間+x,區間*x，查詢區間和
//思路：維護兩個LazyTag
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 100010;
typedef long long LL;int n, m;
LL a[maxn],mod;
struct node{int l, r;LL val, addmark, mulmark;
}sgt[maxn<<2];
void build(int p, int l, int r){sgt[p].l = l, sgt[p].r = r;sgt[p].mulmark=1, sgt[p].addmark=0;if(l == r){sgt[p].val = a[l];}else{int m = (l+r)/2;build(p*2,l,m);build(p*2+1,m+1,r);sgt[p].val = sgt[p*2].val+sgt[p*2+1].val;}sgt[p].val %= mod;
}
void pushdown(int p){if(sgt[p].addmark==0&&sgt[p].mulmark==1)return ;//初始化父節點LL t1 = sgt[p].addmark, t2 = sgt[p].mulmark;sgt[p].addmark = 0, sgt[p].mulmark = 1;//維護標記sgt[p*2].mulmark = (sgt[p*2].mulmark*t2)%mod;sgt[p*2+1].mulmark = (sgt[p*2+1].mulmark*t2)%mod;sgt[p*2].addmark = (sgt[p*2].addmark*t2+t1)%mod;sgt[p*2+1].addmark = (sgt[p*2+1].addmark*t2+t1)%mod;//更新當前值,我們規定乘法優先更新(加法優先會損失精度)int l = sgt[p].l, r = sgt[p].r, m = (l+r)/2;sgt[p*2].val=(sgt[p*2].val*t2+t1*(m-l+1))%mod;//先乘以乘法標記再加上已用乘法標記更新過的加法標記。sgt[p*2+1].val=(sgt[p*2+1].val*t2+t1*(r-m))%mod;
}
void add(int p, int l, int r, LL v){if(l <= sgt[p].l && sgt[p].r <= r){sgt[p].val = (sgt[p].val+(sgt[p].r-sgt[p].l+1)*v)%mod;sgt[p].addmark = (sgt[p].addmark+v)%mod;return ;}pushdown(p);int m = (sgt[p].l+sgt[p].r)/2;if(l <= m)add(p*2,l,r,v);if(r > m)add(p*2+1,l,r,v);sgt[p].val = (sgt[p*2].val+sgt[p*2+1].val)%mod;
}
void times(int p, int l, int r, LL v){if(l <= sgt[p].l && sgt[p].r <= r){sgt[p].val = (sgt[p].val*v)%mod;sgt[p].mulmark = (sgt[p].mulmark*v)%mod;sgt[p].addmark = (sgt[p].addmark*v)%mod;//原先的加法標記也要乘return ;}pushdown(p);int m = (sgt[p].l+sgt[p].r)/2;if(l <= m)times(p*2,l,r,v);if(r > m)times(p*2+1,l,r,v);sgt[p].val = (sgt[p*2].val+sgt[p*2+1].val)%mod;
}
LL query(int p, int l, int r){if(l <= sgt[p].l && sgt[p].r <= r)return sgt[p].val;pushdown(p); //pushdownLL m = (sgt[p].l+sgt[p].r)/2, ans = 0;if(l <= m)ans += query(p*2,l,r);if(r > m)ans += query(p*2+1,l,r);return ans%mod;
}int main(){ios::sync_with_stdio(false);cin>>n>>mod;for(int i = 1; i <= n; i++)cin>>a[i];build(1,1,n);cin>>m;for(int i = 1; i <= m; i++){int op;  cin>>op;if(op == 1){LL x, y, z;  cin>>x>>y>>z;times(1,x,y,z);}else if(op == 2){LL x, y, z;  cin>>x>>y>>z;add(1,x,y,z);}else{LL x, y;  cin>>x>>y;cout<<query(1,x,y)%mod<<"\n";}}return 0;
}

AcWing 256. 最大異或和388人打卡

//題意：維護一個序列，支持末尾加一個數，詢問區間[l,r]中的p,滿足a[p]^a[p+1]...^a[n]^x最大。
//思路：
//+ 首先因為區間異或和，且異或滿足性質a^b^a==b，所以可以想到異或前綴和，s[l~r] = s[r]^s[l-1]。題目轉化為求a[p-1]^s[n]^x最大。
//+ 然后v=s[n]^x為定值，即為求[l-1,r-1]中與之異或最大的值，考慮二進制最高位開始到最低位的每一個數字盡量與v的二進制對應位相反就可以保證異或出來最大。
//+ 綜上，可以將所有s[i]加入01字典樹中，用于尋找最大異或，對于區間查詢，采用可持久化維護。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 6e5+10;
typedef long long LL;int n, m, s[maxn];//可持久化01字典樹
int tire[maxn*24][2], rt[maxn*24], idx, ver[maxn*24];
//第i個版本，上一個版本，當前版本的對應節點，當前這個數第幾位
void insert(int i, int p, int q, int k){if(k<0){ //記錄結束了ver[q] = i;//記錄當前節點(可能會被后面公用)所能到達的最大范圍ireturn ;}int c = s[i]>>k&1;//取出前綴和的二進制表示從右往左數第k位vif(p)tire[q][c^1] = tire[p][c^1];//如果前一個節點存在當前節點沒有的分支, 那就把當前節點的這個空的路徑指過去, 相當于復制tire[q][c] = ++idx;//正常trie樹插入insert(i,tire[p][c],tire[q][c],k-1);//遞歸插入下一位二進制ver[q] = max(ver[tire[q][0]], ver[tire[q][1]]);
}
int query(int l, int r, int C){int p = rt[r];for(int i = 23; i >= 0; i--){int v = C>>i&1;if(ver[tire[p][v^1]] >= l)p = tire[p][v^1];else p = tire[p][v];}return C^s[ver[p]];
}int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;s[0] = 0, ver[0] = -1;rt[0] = ++idx, insert(0,0,rt[0],23);for(int i = 1; i <= n; i++){int x;  cin>>x;  s[i]=s[i-1]^x;rt[i] = ++idx;  insert(i,rt[i-1],rt[i], 23);}while(m--){string op;  cin>>op;if(op=="A"){int x;  cin>>x;n++;  s[n] = s[n-1]^x;rt[n] = ++idx;  insert(n,rt[n-1],rt[n], 23);}else{int l, r, x;  cin>>l>>r>>x;cout<<query(l-1, r-1, s[n]^x)<<"\n";}}return 0;
}

AcWing 255. 第K小數428人打卡

//題意：區間靜態第k小。有n個數，多次詢問一個區間[L,R]中第k小的值是多少。
//思路：可持久化線段樹 2（主席樹）模板
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;int a[maxn], b[maxn];int rt[maxn], lch[maxn<<5], rch[maxn<<5], sum[maxn<<5], tot;//主席樹
void build(int &p, int l, int r){p = ++tot;if(l==r)return ;int mid = (l+r)>>1;build(lch[p], l, mid);build(rch[p], mid+1, r);
}
int update(int p, int l, int r, int x){	//b[x]+=1;int np = ++tot;lch[np]=lch[p], rch[np] = rch[p], sum[np] = sum[p]+1;if(l==r)return np;int mid = (l+r)>>1;if(x<=mid)lch[np] = update(lch[np], l, mid, x);else rch[np] = update(rch[np], mid+1, r, x);return np;
}
int query(int u, int v, int l, int r, int k){int ans, mid=(l+r>>1), x=sum[lch[v]]-sum[lch[u]];if(l==r)return l;if(x>=k)ans = query(lch[u], lch[v], l, mid, k);else ans = query(rch[u], rch[v], mid+1, r, k-x);return ans;
}int main(){int n, q;  cin>>n>>q;for(int i = 1; i <= n; i++)cin>>a[i], b[i]=a[i];sort(b+1,b+n+1);int m = unique(b+1,b+n+1)-b-1;build(rt[0], 1, m);						   //用離散化后的數據建立初始的值域線段樹,區間加維護每個元素(位置)的出現次數for(int i = 1; i <= n; i++){int p = lower_bound(b+1,b+m+1, a[i])-b;//查詢a[i]離散化后對應的值rt[i] = update(rt[i-1], 1, m, p);	   //建立第i個版本的值域線段樹,維護[1,i]時，每個區間的元素個數}while(q--){int l, r, k;  cin>>l>>r>>k;int ans = query(rt[l-1],rt[r],1,m,k); //查詢用第r個版本和第l-1個版本之間值域差值查cout<<b[ans]<<"\n";					  //返回離散化對應的值}return 0;
}

AcWing 253. 普通平衡樹415人打卡

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T;  cin>>T;vector<int>a;while(T--){int op, x;  cin>>op>>x;if(op==1){a.insert(upper_bound(a.begin(),a.end(),x),x);}else if(op==2){a.erase(lower_bound(a.begin(),a.end(),x));}else if(op==3){cout<<lower_bound(a.begin(),a.end(),x)-a.begin()+1<<endl;}else if(op==4){cout<<a[x-1]<<endl;}else if(op==5){cout<<*--lower_bound(a.begin(),a.end(),x)<<endl;}else{cout<<*upper_bound(a.begin(),a.end(),x)<<endl;}}return 0;
}

AcWing 265. 營業額統計344人打卡

//題意：定義第i天的最小波動值為min{|a[i]-a[j]|, j<i}，求每天的最小波動值和
//思路：set維護之前的營業額，每次二分前驅和后繼，暴力計算。
#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n;  cin>>n;set<int>se;se.insert(-1e9); se.insert(1e9);int ans = 0;for(int i = 1; i <= n; i++){int x;  cin>>x;if(i==1){ ans += x;  se.insert(x); }if(se.count(x)){//波動為0continue;}else{auto a = se.lower_bound(x);//找>=x的第一個數if(*a != x){			   //!=x，所以是大于x的第一個數auto b = a;  b--;	   //小于x的第一個數ans += min(abs(*b-x), abs(*a-x)); //前驅和后繼取最小se.insert(x);}}}cout<<ans<<"\n";return 0;
}

AcWing 1282. 搜索關鍵詞441人打卡

//題意：給定n個長度不超過50的單詞，以及一篇長為m的文章，問有多少個單詞在文章中出現。
//思路：單詞丟進自動機建fail樹，然后拿文章匹配一下。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
char s[maxn*100];
int ch[maxn*50][26], cnt[maxn*50], tot, fail[maxn*50];
struct ac{void ins(){//字典樹scanf("%s",s+1); int now=0, len=strlen(s+1);for(int i = 1; i <= len; i++){int u = s[i]-'a';if(!ch[now][u])ch[now][u] = ++tot;now = ch[now][u];}cnt[now]++;}void build(){//fail樹queue<int>q;for(int i=0; i < 26; i++)if(ch[0][i])q.push(ch[0][i]);while(q.size()){int x = q.front(); q.pop();for(int i = 0; i < 26; i++){int y = ch[x][i];if(y){fail[y] = ch[fail[x]][i];q.push(y);}else{ch[x][i] = ch[fail[x]][i];}}}}void solve(){//匹配int res = 0;int len = strlen(s+1), now = 0;for(int i=1; i<=len; i++){int u = s[i]-'a';now = ch[now][u];int p = now;while(p){res += cnt[p];cnt[p] = 0;p = fail[p];}}cout<<res<<"\n";}void init(){memset(ch,0,sizeof(ch));memset(cnt,0,sizeof(cnt));memset(fail,0,sizeof(fail));}
}ac;int main(){//ios::sync_with_stdio(0);//, cin.tie(0), cout.tie(0);WAint T;  cin>>T;while(T--){ac.init();int n;  cin>>n;for(int i = 1; i <= n; i++)ac.ins();ac.build();scanf("%s",s+1);ac.solve();}return 0;
}

AcWing 1285. 單詞297人打卡

//題意：給出n個單詞和n個與之相同的模式串進行匹配，求出各個單詞匹配的出現次數
//思路：跑一遍AC自動機，每一個節點保存一下屬于多少字符串，為它的權值。然后一個節點表示的字符串在整個字典中出現的次數相當于其在Fail樹中的子樹的權值的和
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1100005;int n;
char s[maxn];
int ch[maxn][26], sz[maxn], cnt;
int a[maxn], h[maxn], fail[maxn];
struct ac{void ins(int x){scanf("%s",s+1); int now=0, len=strlen(s+1);for(int i = 1; i <= len; i++){int u = s[i]-'a';if(!ch[now][u])ch[now][u] = ++cnt;now = ch[now][u];sz[now]++;}a[x] = now;}void build(){int head=0, tail = 0;for(int i=0; i < 26; i++)if(ch[0][i])h[++tail]=ch[0][i];while(head < tail){int x=h[++head], y;for(int i = 0; i < 26; i++){if(ch[x][i]){y = ch[x][i];h[++tail] = y;fail[y] = ch[fail[x]][i];}else{ch[x][i] = ch[fail[x]][i];}}}}void solve(){for(int i=cnt; i >= 0; i--)sz[fail[h[i]]]+=sz[h[i]];for(int i = 1; i <= n; i++)cout<<sz[a[i]]<<"\n";}
}ac;int main(){//ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);WAcin>>n;for(int i=1; i<=n; i++)ac.ins(i);ac.build();ac.solve();return 0;
}