2018 - 2019 SEERC 題解

比賽發(fā)出來太新了,網(wǎng)上根本就搜不到題解,補(bǔ)題補(bǔ)的太難受了.
在這里分享一篇我自己寫的題解,也方便別人補(bǔ)題.

題目鏈接

http://codeforces.com/gym/101964/attachments/download/7814/seerc-2018.pdf

---

A.Numbers

不留坑,這題不會(huì).

---

B.Broken Watch

題解

先考慮三個(gè)針長(zhǎng)度各不一樣的情況.

注意到需要對(duì)$n$分奇偶性進(jìn)行討論.

$n$為偶數(shù)的時(shí)候,固定$1$號(hào)針的位置,枚舉$2$號(hào)針的位置,那么$3$號(hào)針的位置必然在$1,2$號(hào)針的反向延長(zhǎng)線形成的扇形區(qū)域內(nèi)(可與邊界重合).
并注意到當(dāng)$1,2$號(hào)針反向的時(shí)候,$3$號(hào)針有$n?2$種取法.
可以得到公式$n(1+2+...+\frac{n}{2}+n?2)$.

$n$為奇數(shù)的時(shí)候,固定$1$號(hào)針的位置枚舉$2$號(hào)針的位置,那么$3$號(hào)針的位置必然在$1,2$號(hào)針反向延長(zhǎng)線之間(不能與邊界重合).
可以得到公式$n(1+2+...+?\frac{n}{2}?)$

而當(dāng)三根針有兩根相同時(shí),需要對(duì)答案除以$2!$,當(dāng)三根全都相同時(shí),需要對(duì)答案除以$3!$,這題就結(jié)束了.不明白為什么這個(gè)題比$C$題過得人少?

代碼

org = input().split(" ")a = int(org[0]) b = int(org[1]) c = int(org[2]) n = int(org[3])len = 1if a == b and b == c:len = 6 elif a == b or b == c or a == c:len = 2mod = 2**64ans = 0 if n % 2 == 0:ans = (n*((n//2-1)*(n//2+2)+(n-2))//len )% mod else:ans = (n*(n//2)*(n//2+1)//len) % modprint(ans)

---

C.Tree

題解

訓(xùn)練的時(shí)候想了一種樹dp的做法,不太好調(diào),幸好最后還是A掉了.賽后翻比別人代碼發(fā)現(xiàn)還有一種很巧妙地方法,即枚舉樹的直徑.兩種方法我都簡(jiǎn)略說一下.

方法一.樹dp

二分最大距離$M$,然后樹$dp$來$check$可行性.

定義$dp[i][j]$表示以$i$為根的子樹,選出來的黑點(diǎn)中距$i$節(jié)點(diǎn)距離不會(huì)超過$j$,所能選出最多的黑點(diǎn)個(gè)數(shù).
并記$lim=MIN\{M?1?j,j?1\}$
那么轉(zhuǎn)移就是:
假設(shè)$v_1,v_2,...,v_m$是$i$的兒子節(jié)點(diǎn).

$MI{N}_{1\le p\le m}\{dp[v_p][j?1]+{\sum }_{q!=p}dp[v_q][lim]\}\to dp[i][j]$

$dp[i][j?1]\to dp[i][j]$

最后只要看$dp[1][M]\ge k$.

時(shí)間復(fù)雜度?
$O(n^{3}log(n))$

方法二.枚舉樹的直徑

先預(yù)處理出樹上兩點(diǎn)之間的距離(使用Floyd算法即可).

注意到將黑點(diǎn)取出之后會(huì)形成一顆虛樹,并且兩兩之間最長(zhǎng)的距離就是

然后我們考慮枚舉這顆虛樹的直徑,假設(shè)是$(i,j)$,然后再枚舉黑點(diǎn),黑點(diǎn)進(jìn)到虛樹中一定不能使直徑邊長(zhǎng).所以就要要求$dis[i][k]\le dis[i][j]\&\&dis[k][j]\le dis[i][j]$.

時(shí)間復(fù)雜度$O(n^3)$

這個(gè)方法簡(jiǎn)單多了.

注意:不需要建虛樹,說虛樹主要是好描述.

代碼

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #define pr(x) std::cout << #x << ':' << x << std::endl #define rep(i,a,b) for(int i = a;i <= b;++i)using namespace std;const int maxn = 105; int n,m,val[maxn],dp[maxn][maxn]; vector<int> G[maxn];void dfs(int cur,int pre,int mid){for(int nx : G[cur]) if(nx != pre) dfs(nx,cur,mid);if(val[cur] == 1) dp[cur][0] = 1;for(int i = 1;i <= mid;i++){int limit = min(mid-1-i,i-1), sum = 0;if(limit >= 0) for(int nx : G[cur]) if(nx != pre){sum += dp[nx][limit];}dp[cur][i] = max(dp[cur][i],dp[cur][i-1]);for(int nx : G[cur]){if(nx == pre) continue;int tmp = dp[nx][i-1];if(limit >= 0) tmp += sum - dp[nx][limit];dp[cur][i] = max(dp[cur][i], val[cur]+tmp);}} } bool check(int mid){memset(dp,0,sizeof(dp));dfs(1,-1,mid);int f = 0;for(int i = 1;i <= n;++i)f |= dp[i][mid] >= m;return f; }int main(){ios::sync_with_stdio(false);cin>>n>>m;for(int i = 1;i <= n;i++) cin>>val[i];for(int i = 0;i < n-1;i++){int u,v;cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}int l = 0, r = n;while(r - l > 1){int mid = (l + r) >> 1;if(check(mid)) r = mid;else l = mid + 1;}if(check(l)) cout<<l<<endl;else cout<<r<<endl;return 0; }

---

D.Space Station

題解

一道很神奇的題,需要先猜出結(jié)論,然后再進(jìn)行樹上背包.思路弄清楚了實(shí)現(xiàn)起來很簡(jiǎn)單.

簡(jiǎn)述一下題意:一顆$n$個(gè)結(jié)點(diǎn)的帶權(quán)樹,要求從$1$號(hào)點(diǎn)出發(fā),遍歷所有的邊,然后回到$1$號(hào)點(diǎn).途中可以最多使用$m$次技能,技能花費(fèi)時(shí)間為$k$,功能是在任意兩點(diǎn)中穿越.求最小代價(jià).

我們先來發(fā)現(xiàn)一些規(guī)律性的東西.

注意到一顆子樹如果子樹中包含的技能出發(fā)點(diǎn)和技能到達(dá)點(diǎn)共$p$個(gè),如果$p$是偶數(shù)的時(shí)候,那么這顆子樹根節(jié)點(diǎn)的父親邊一定要走兩次(可以畫圖幫助理解一下)

而如果$p$是奇數(shù)的話,那么子樹根節(jié)點(diǎn)的父親邊只需要走一次就好了.(畫圖幫助理解)

這就很簡(jiǎn)單了.

定義$dp[i][j]$表示以$i$為根的子樹,其子樹中奇點(diǎn)個(gè)數(shù)為$j$,從$i$點(diǎn)出發(fā)遍歷完$i$的子樹再回到$i$點(diǎn),所需要的最小代價(jià).

那么轉(zhuǎn)移方程就是

${\sum }_{p_1+p_2+...+p_m=j}(dp[v_i][p_i]+(![p_i\&1]+1)?c_i)\to dp[u][j]$

${\sum }_{p_1+p_2+...+p_m=j}(dp[v_i][p_i]+(![p_i\&1]+1)?c_i)\to dp[u][j+1]$

代碼

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #define pr(x) std::cout << #x << ':' << x << std::endl #define rep(i,a,b) for(int i = a;i <= b;++i) typedef std::pair<int,int> pii; const int N = 1007; std::vector<pii> edge[N]; int dp[N][N],sz[N],tmp[N]; int n,m,k,T; void upd(int &x,int y){if(y < x) x = y; } void dfs(int u,int fa) {sz[u] = 1;for(pii p : edge[u]) {int v = p.first,c = p.second;if(v == fa) continue;dfs(v,u);memset(tmp,0x3f,sizeof(tmp));for(int i = 0;i <= sz[u];++i) {for(int j = 0;j <= sz[v];++j) {if(i + j > 2*m) continue;if(j % 2 != 0) {upd(tmp[i+j],dp[u][i] + dp[v][j] + c);upd(tmp[i+j+1],dp[u][i] + dp[v][j] + c);}else {upd(tmp[i+j],dp[u][i] + dp[v][j] + 2*c);upd(tmp[i+j+1],dp[u][i] + dp[v][j] + 2*c);}}}sz[u] += sz[v];for(int i = 0;i <= sz[u];++i)dp[u][i] = tmp[i];} }int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cin >> T;while(T--) {std::cin >> n >> m >> k;memset(dp,0,sizeof(dp));rep(i,1,n) edge[i].clear();rep(i,1,n-1) {int u,v,c;std::cin >> u >> v >> c;edge[u].push_back((pii){v,c});edge[v].push_back((pii){u,c});}dfs(1,0);int ans = 0x3f3f3f3f;for(int i = 0;i <= std::min(2*m,n);i += 2) upd(ans,dp[1][i]+(i/2*k));std::cout << ans << std::endl;}return 0; }

---

E.Fisherman

題解

首先我們將釣魚的人按照$x$坐標(biāo)排個(gè)序，同時(shí)也記錄一下他在答案里的順序以便逆映射回去。
然后考慮每一條魚能被哪些漁夫釣到，也就是考慮貢獻(xiàn)。我們能夠很簡(jiǎn)單地知道，一條魚能夠被釣到的地方在$x$軸上是一段連續(xù)的區(qū)間。當(dāng)魚的y坐標(biāo)大于所給的線的長(zhǎng)度時(shí)釣不到，否則記魚線長(zhǎng)度大于$y$坐標(biāo)的長(zhǎng)度$l?y=dl$，能夠釣到魚區(qū)間即為$[x?dl,x+dl]$。于是lower_bound和upper _bound找一下漁夫里面所對(duì)應(yīng)的區(qū)間，然后區(qū)間加單點(diǎn)查詢。區(qū)間加單點(diǎn)查詢這個(gè)操作在代碼里是使用了差分?jǐn)?shù)組來維護(hù)的，最后算完之后把差分?jǐn)?shù)組還原即可得到答案。

---

F.Min Max Convert

題解

大致的題意是給你兩個(gè)長(zhǎng)為$n$的數(shù)列$A,B$,然后你每次可以選擇一段區(qū)間將區(qū)間覆蓋成它的最大值或者是覆蓋成它的最小值.要求輸出一個(gè)長(zhǎng)不超過$2n$的方案,將$A$數(shù)列變成$B$數(shù)列.

很明顯的構(gòu)造題.

我們首先要找一下規(guī)律以發(fā)現(xiàn)一些結(jié)論.

一個(gè)區(qū)間最多通過兩次操作可以將區(qū)間覆蓋為區(qū)間中任意一個(gè)數(shù).
當(dāng)$v$在區(qū)間邊界上時(shí),例如$v=a[l]$,將$[l,r]$覆蓋為$v$的方法是:判斷$a[l]$和$a[l+1]$的大小關(guān)系,如果$a[l]>a[l+1]$,那么就將$[l+1,r]$取最小值,再將$[l,r]$取最大值.
當(dāng)$v$在$[l,r]$中間時(shí),可以將區(qū)間分成兩段,分別操作.

對(duì)于$B$數(shù)列的每個(gè)數(shù),在$A$數(shù)列中都應(yīng)該有一個(gè)數(shù)與它對(duì)應(yīng).并且這些對(duì)應(yīng)關(guān)系不交叉.
比如:
$A:5,3,1,2,2,4,7,6,8,6$
$B:1,1,2,4,4,7,7,8,8,8$
那么對(duì)應(yīng)關(guān)系是這樣的:

好難講,直接看我代碼吧.

代碼

#include <iostream> #include <algorithm> #include <cstring> #define pr(x) std::cout << #x << ':' << x << std::endl #define rep(i,a,b) for(int i = a;i <= b;++i)const int N = 100007; int A[N],B[N],Loc[N]; char C[N<<1];int L[N<<1],R[N<<1]; int tot; struct E{int b,e,x; }es[N]; int etot = 0; int n; void Do(char c,int l,int r) {C[tot] = c;L[tot] = l;R[tot] = r;++tot; } int main() {scanf("%d",&n);rep(i,1,n) scanf("%d",&A[i]);rep(i,1,n) scanf("%d",&B[i]);int pos = 1;rep(i,1,n) {while(pos <= n && A[pos] != B[i]) pos ++;if(pos == n+1) return 0*puts("-1");Loc[i] = pos; }int p = 1;rep(i,1,n) {if(Loc[i] != Loc[i+1]) {es[etot++] = (E){p,i,Loc[i]};p = i+1;}}for(int i = etot-1;i >= 0;--i) {if(es[i].x < es[i].b) {if(A[es[i].x] >= A[es[i].x+1]) {Do('m',es[i].x+1,es[i].e);Do('M',es[i].x,es[i].e);}if(A[es[i].x] < A[es[i].x+1]) {Do('M',es[i].x+1,es[i].e);Do('m',es[i].x,es[i].e);}}}rep(i,0,etot-1) {if(es[i].x > es[i].e) {if(A[es[i].x] <= A[es[i].x-1]) {Do('M',es[i].b,es[i].x-1);Do('m',es[i].b,es[i].x);} if(A[es[i].x] > A[es[i].x-1]) {Do('m',es[i].b,es[i].x-1);Do('M',es[i].b,es[i].x);}}}rep(i,0,etot-1) {if(es[i].b <= es[i].x && es[i].x <= es[i].e) {if(es[i].x > es[i].b && A[es[i].x] >= A[es[i].x-1]) {Do('m',es[i].b,es[i].x-1);Do('M',es[i].b,es[i].x);}if(es[i].x > es[i].b && A[es[i].x] < A[es[i].x-1]) {Do('M',es[i].b,es[i].x-1);Do('m',es[i].b,es[i].x);}if(es[i].x < es[i].e && A[es[i].x] >= A[es[i].x+1]) {Do('m',es[i].x+1,es[i].e);Do('M',es[i].x,es[i].e);}if(es[i].x < es[i].e && A[es[i].x] < A[es[i].x+1]) {Do('M',es[i].x+1,es[i].e);Do('m',es[i].x,es[i].e);}}}std::cout << tot << std::endl;rep(i,0,tot-1) {printf("%c %d %d\n",C[i],L[i],R[i]);}return 0; }

---

G.Matrix Queries

題解

隊(duì)友$LNC$寫的.

結(jié)論：我們稱依題目給出的公式計(jì)算矩陣$A$的得分時(shí)遞歸處理到的矩陣均稱為$A$的“子矩陣”，記這些矩陣中有$n$個(gè)為不“純色”的矩陣，則矩陣A的得分為$4n+1$。

證明：
用數(shù)學(xué)歸納法：當(dāng)$A$為$1\times 1$的矩陣時(shí)顯然結(jié)論成立。
假設(shè)A為$2^k\times 2^k$的矩陣時(shí)結(jié)論成立，現(xiàn)證A為$2^{k+1}\times 2^{k+1}$矩陣時(shí)結(jié)論仍成立：

$A$純色，則其得分為1，結(jié)論成立；

$A$不純色，記其四個(gè)子矩陣的不純色的子矩陣個(gè)數(shù)分別為$n_1$、$n_2$、$n_3$和$n_4$，則由假設(shè)它們的得分分別為$4n_1+1$、$4n_2+1$、$4n_3+1$和$4n_4+1$，A中不純色的子矩陣個(gè)數(shù)為$n_1+n_2+n_3+n_4+1$，由定義A的得分$s=5+(n_1+n_2+n_3+n_4)=4(n_1+n_2+n_3+n_4+1)+1$，結(jié)論成立。

綜上結(jié)論得證。

考慮到一個(gè)矩陣為純色則這個(gè)矩陣的每行需修改相同奇偶次且每列也需修改相同奇偶次，統(tǒng)計(jì)有多少合法位置的連續(xù)$2^k$行與列修改的奇偶次數(shù)相同，相乘結(jié)果即$2^k\times 2^k$大小矩陣中純色的個(gè)數(shù)，求反面即可。這些區(qū)間形成了線段樹的結(jié)構(gòu)，用線段樹維護(hù)即可。

代碼

#include <bits/stdc++.h> using namespace std;typedef long long ll; const int maxn = (1<<20)+10; ll seg[2][maxn*4],ans[2][21];void modify(int id,int o,int l,int r,int deep,int x){if(l == r){seg[id][o] ^= 1;return;}int mid = (l + r) >> 1;if(x <= mid) modify(id,o<<1,l,mid,deep+1,x);else modify(id,o<<1|1,mid+1,r,deep+1,x);if(seg[id][o] != -1) ans[id][deep]--;if(seg[id][o<<1] == seg[id][o<<1|1]) seg[id][o] = seg[id][o<<1];else seg[id][o] = -1;if(seg[id][o] != -1) ans[id][deep]++; } inline void read(int& x){char ch = getchar();x = 0;for(;ch < '0' || ch > '9';ch = getchar());for(;ch >= '0' && ch <= '9';ch = getchar()) x = x*10+(ch-'0'); } inline void write(ll x){char ch = x%10+'0';if(x >= 10) write(x/10);putchar(ch); }int main(){ios::sync_with_stdio(false);int n,m,sz;ll sum = 0;read(sz);read(m);n = (1 << sz);for(int i = 0;i < sz;i++){ans[0][i+1] = ans[1][i+1] = (1 << i);sum += (1ll << (i * 2)); }for(int i = 0;i < m;i++){int id, x;read(id);read(x);modify(id,1,1,n,1,x);ll tmp = 0;for(int i = 1;i <= sz;i++){tmp += 1ll*ans[0][i] * ans[1][i];}write(4ll * (sum - tmp) + 1);puts("");}return 0; }

---

H.Modern Djinn

題解

留坑.

---

I.Inversion

題解

第一步,根據(jù)圖恢原來的排列.

在得到原來的排列以后,我們從排列中挑選一些位置$(p_1,p_2,...p_m)$組成一個(gè)獨(dú)立支配集.必然有$a[p_1]<a[p_2]<...<a[p_m]$,只有這樣,集合里的點(diǎn)之間才沒有邊相連,并且還要滿足條件即$[p_i,p_{i+1}]$之間的數(shù)要么大于$a[p_{i+1}]$,要么小于$a[i]$.

并且在排列中不可能存在$p_0<p_1并且a[p_0]<a[p_1]$,否則的話,它也應(yīng)該存在于集合當(dāng)中,應(yīng)為它與集合中的所有點(diǎn)都無邊相連.同理,不存在$p_{m+1}>p_m$,使得$a[p_{m+1}]>a[p_m]$.

如果$p<q且a[p]<a[q]且a[p,q]$之間的數(shù)不會(huì)存在介于$a[p]$與$a[q]$之間的數(shù),就從$p$向$q$連邊.

答案就是從入度為$0$的點(diǎn),跑到出度為$0$的點(diǎn)的路徑數(shù)之和.

拓?fù)湫騞p一下結(jié)束.

代碼

#include <bits/stdc++.h> using namespace std;typedef long long ll; const int maxn = 105; int a[maxn], in[maxn], cnt, x[maxn],n,m; ll dp[maxn]; bool vis[maxn][maxn]; vector<int> G[maxn];ll dfs(int cur){if(dp[cur] != -1) return dp[cur];dp[cur] = 0;if(G[cur].size() == 0) dp[cur]++;for(int nx : G[cur]){dp[cur] += dfs(nx);}return dp[cur]; }int main(){ios::sync_with_stdio(false);cin>>n>>m;for(int i = 0;i < m;i++){int u,v;cin>>u>>v;vis[u][v] = vis[v][u] = 1;if(u < v) swap(u,v);G[u].push_back(v);in[v]++;}for(int i = 1;i <= n;i++){for(int j = i+1;j <= n;j++){if(vis[i][j]) continue;G[i].push_back(j);in[j]++;}}queue<int> q;for(int i = 1;i <= n;i++){if(in[i] == 0) q.push(i);}while(!q.empty()){int cur = q.front();q.pop();a[cur] = ++cnt;for(int nx : G[cur]){in[nx]--;if(in[nx] == 0) q.push(nx);}}memset(in,0,sizeof(in));for(int i = 1;i <= n;i++) G[i].clear();for(int i = 1;i <= n;i++){for(int j = i+1;j <= n;j++){if(a[i] > a[j]) continue;bool flag = true;for(int k = i + 1;k < j;k++)if(a[k] > a[i] && a[k] < a[j]) flag = false;if(flag){G[i].push_back(j);in[j]++;}}}ll ans = 0;memset(dp,-1,sizeof(dp));for(int i = 1;i <= n;i++) if(in[i] == 0) ans += dfs(i);cout<<ans<<endl;return 0; }

---

J.Rabbit vs Turtle

題解

留坑

---

K.Points and Rectangles

題解

$cdq$分治的一道比較裸的題.

像這種能用二維線段樹做的題(空間爆炸)都可以轉(zhuǎn)換成離線cdq分治去解決.

每個(gè)點(diǎn)算作$1$個(gè)$event$.

每個(gè)矩形按照左邊和右邊拆成兩個(gè)$event$,每個(gè)$event$包含上下邊界.

我們考慮單獨(dú)對(duì)點(diǎn)和矩形算貢獻(xiàn).

對(duì)矩形算貢獻(xiàn):
所有在該矩形前加的點(diǎn)都對(duì)矩形的左邊$event$有$1$個(gè)負(fù)的影響,對(duì)矩形的右邊$event$有$1$個(gè)正的貢獻(xiàn).
維護(hù)一個(gè)樹狀數(shù)組,$i$位置的值代表目前存在的點(diǎn)$y$值為$i$的有多少個(gè).
那么對(duì)于每一個(gè)分治過程按照$event$的$x$從小到大的過程掃過來,遇見矩形左邊$event$就將貢獻(xiàn)減去$sum[down,up]$,遇見矩形右邊$event$,就將貢獻(xiàn)加上$sum[down,up]$.
需要注意的一點(diǎn)是當(dāng)多個(gè)$event$的$x$相同的情況下,我們按照矩形左邊$event$,點(diǎn)$event$,矩形右邊$event$ 順序掃.

對(duì)點(diǎn)算貢獻(xiàn).
矩形的左邊$event$對(duì)點(diǎn)會(huì)產(chǎn)生正的貢獻(xiàn),而矩形的右邊$event$會(huì)對(duì)點(diǎn)產(chǎn)生負(fù)的貢獻(xiàn).
還是按照$event$的$x$值從小到大的過程掃過來,遇見矩形左邊$event$就將新樹狀數(shù)組的$down$位置$+1$,將$up+1$位置$?1$.
遇見矩形右邊$event$就將新樹狀數(shù)組的$down$位置$?1$,將$up+1$位置$+1$.
在遇見點(diǎn)$event$時(shí)候,直接統(tǒng)計(jì)$sum[0,y]$的值就是包含這個(gè)點(diǎn)的矩形的貢獻(xiàn).
需要注意的一點(diǎn)是當(dāng)多個(gè)$event$的$x$相同的情況下,我們按照矩形左邊$event$,點(diǎn)$event$,矩形右邊$event$ 順序掃.

代碼

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #define pr(x) std::cout << #x << ':' << x << std::endl #define rep(i,a,b) for(int i = a;i <= b;++i) #define int long long int op[3] = {2,1,3}; const int N = 1e6; struct event{int tp,id,x,up,down;event(int tp=0,int id=0,int x=0,int up=0,int down=0):tp(tp),id(id),x(x),up(up),down(down){}friend bool operator<(event &e1,event &e2) {return e1.x == e2.x ? (op[e1.tp] < op[e2.tp]) : (e1.x < e2.x);} }es[N<<1]; int tot;int a[N],ans[N]; int bit1[N],bit2[N]; int ec = 0,q;event tmp[N<<1];int lowbit(int x) {return x & (-x); }void add(int bit[],int pos,int x) {for(;pos < N;pos += lowbit(pos))bit[pos] += x; }int sum(int bit[],int pos) {int res = 0;for(;pos;pos -= lowbit(pos)) {res += bit[pos];}return res; }void clr(int bit[],int pos) {if(pos <= 0) return ;for(;pos < N;pos += lowbit(pos))bit[pos] = 0; }void solve(int l,int r) {if(l == r) return ;int mid = (l + r) >> 1;solve(l,mid);solve(mid+1,r);std::vector<int> vec1,vec2;int s = 0,p = l,q = mid+1;while(p <= mid && q <= r) {if(es[p] < es[q]) {if(es[p].tp == 0) {add(bit1,es[p].up,1);vec1.push_back(es[p].up);}else if(es[p].tp == 1) {add(bit2,es[p].down,1);add(bit2,es[p].up+1,-1);vec2.push_back(es[p].down);vec2.push_back(es[p].up+1);}else if(es[p].tp == 2) {add(bit2,es[p].down,-1);add(bit2,es[p].up+1,1);vec2.push_back(es[p].down);vec2.push_back(es[p].up+1);}tmp[s++] = es[p++];}else {if(es[q].tp == 0) {ans[es[q].id] += sum(bit2,es[q].up);}else if(es[q].tp == 1) {ans[es[q].id] -= sum(bit1,es[q].up) - sum(bit1,es[q].down-1);}else if(es[q].tp == 2) {ans[es[q].id] += sum(bit1,es[q].up) - sum(bit1,es[q].down-1);}tmp[s++] = es[q++];}}while(p <= mid) tmp[s++] = es[p++];while(q <= r){if(es[q].tp == 0) {ans[es[q].id] += sum(bit2,es[q].up);}else if(es[q].tp == 1) {ans[es[q].id] -= sum(bit1,es[q].up) - sum(bit1,es[q].down-1);}else if(es[q].tp == 2)ans[es[q].id] += sum(bit1,es[q].up) - sum(bit1,es[q].down-1);tmp[s++] = es[q++];}for(int x : vec1) clr(bit1,x);for(int x : vec2) clr(bit2,x);rep(i,l,r) {es[i] = tmp[i-l];} }signed main() {std::ios::sync_with_stdio(false);std::cin >> q;a[ec++] = 0;rep(i,1,q) {int tp;std::cin >> tp;if(tp == 1) {int x,y;std::cin >> x >> y;x+=2,y+=2;a[ec++] = x;a[ec++] = y;es[tot++] = event(0,i,x,y,0);} else if(tp == 2) {int _a,_b,_c,_d;std::cin >> _a >> _b >> _c >> _d;_a+=2,_b+=2,_c+=2,_d+=2;a[ec++] = _a;a[ec++] = _b;a[ec++] = _c;a[ec++] = _d;es[tot++] = event(1,i,_a,_d,_b);es[tot++] = event(2,i,_c,_d,_b);}} std::sort(a,a+ec);ec = std::unique(a,a+ec)-a;for(int i = 0;i < tot;++i) {es[i].x = std::lower_bound(a,a+ec,es[i].x)-a;es[i].up = std::lower_bound(a,a+ec,es[i].up)-a;es[i].down = std::lower_bound(a,a+ec,es[i].down)-a;}solve(0,tot-1);rep(i,1,q) {ans[i] += ans[i-1];std::cout << ans[i] << std::endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2018-2019 ACM—ICPC SEERC 题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。