建设销售型网站,上市公司的信息网站,电子商务网站建设实训方案,软件外包价格2018 - 2019 SEERC 题解 比赛发出来太新了,网上根本就搜不到题解,补题补的太难受了. 在这里分享一篇我自己写的题解,也方便别人补题. 题目链接
http://codeforces.com/gym/101964/attachments/download/7814/seerc-2018.pdf A.Numbers
不留坑,这题不会. B.Broken Watch
题解…2018 - 2019 SEERC 题解 比赛发出来太新了,网上根本就搜不到题解,补题补的太难受了. 在这里分享一篇我自己写的题解,也方便别人补题. 题目链接
http://codeforces.com/gym/101964/attachments/download/7814/seerc-2018.pdf A.Numbers
不留坑,这题不会. B.Broken Watch
题解
先考虑三个针长度各不一样的情况.
注意到需要对nnn分奇偶性进行讨论.
nnn为偶数的时候,固定111号针的位置,枚举222号针的位置,那么333号针的位置必然在1,21,21,2号针的反向延长线形成的扇形区域内(可与边界重合). 并注意到当1,21,21,2号针反向的时候,333号针有n−2n-2n−2种取法. 可以得到公式n(12...n2n−2)n(12...\frac{n}{2} n-2)n(12...2nn−2).nnn为奇数的时候,固定111号针的位置枚举222号针的位置,那么333号针的位置必然在1,21,21,2号针反向延长线之间(不能与边界重合). 可以得到公式n(12...⌊n2⌋)n(12...\lfloor \frac{n}{2} \rfloor)n(12...⌊2n⌋)
而当三根针有两根相同时,需要对答案除以2!2!2!,当三根全都相同时,需要对答案除以3!3!3!,这题就结束了.不明白为什么这个题比CCC题过得人少?
代码
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//22)(n-2))//len )% mod
else:ans (n*(n//2)*(n//21)//len) % modprint(ans)C.Tree
题解
训练的时候想了一种树dp的做法,不太好调,幸好最后还是A掉了.赛后翻比别人代码发现还有一种很巧妙地方法,即枚举树的直径.两种方法我都简略说一下.
方法一.树dp
二分最大距离MMM,然后树dpdpdp来checkcheckcheck可行性.
定义dp[i][j]dp[i][j]dp[i][j]表示以iii为根的子树,选出来的黑点中距iii节点距离不会超过jjj,所能选出最多的黑点个数. 并记limMIN{M−1−j,j−1}lim MIN\{M-1-j,j-1\}limMIN{M−1−j,j−1} 那么转移就是: 假设v1,v2,...,vmv_1,v_2,...,v_mv1,v2,...,vm是iii的儿子节点. MIN1≤p≤m{dp[vp][j−1]∑q!pdp[vq][lim]}→dp[i][j]MIN_{1\le p \le m}\{dp[v_p][j-1] \sum_{q ! p}dp[v_q][lim]\} \rightarrow dp[i][j]MIN1≤p≤m{dp[vp][j−1]∑q!pdp[vq][lim]}→dp[i][j] dp[i][j−1]→dp[i][j]dp[i][j-1] \rightarrow dp[i][j]dp[i][j−1]→dp[i][j]
最后只要看dp[1][M]≥kdp[1][M] \ge kdp[1][M]≥k.
时间复杂度? O(n3log(n))O(n^3log(n))O(n3log(n))
方法二.枚举树的直径
先预处理出树上两点之间的距离(使用Floyd算法即可).
注意到将黑点取出之后会形成一颗虚树,并且两两之间最长的距离就是
然后我们考虑枚举这颗虚树的直径,假设是(i,j)(i,j)(i,j),然后再枚举黑点,黑点进到虚树中一定不能使直径边长.所以就要要求dis[i][k]≤dis[i][j]amp;amp;dis[k][j]≤dis[i][j]dis[i][k] \le dis[i][j] \amp;\amp; dis[k][j] \le dis[i][j]dis[i][k]≤dis[i][j]dis[k][j]≤dis[i][j].
时间复杂度O(n3)O(n^3)O(n3)
这个方法简单多了.
注意:不需要建虚树,说虚树主要是好描述.
代码
#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];
vectorint 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);cinnm;for(int i 1;i n;i) cinval[i];for(int i 0;i n-1;i){int u,v;cinuv;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)) coutlendl;else coutrendl;return 0;
}D.Space Station
题解
一道很神奇的题,需要先猜出结论,然后再进行树上背包.思路弄清楚了实现起来很简单.
简述一下题意:一颗nnn个结点的带权树,要求从111号点出发,遍历所有的边,然后回到111号点.途中可以最多使用mmm次技能,技能花费时间为kkk,功能是在任意两点中穿越.求最小代价.
我们先来发现一些规律性的东西.
注意到一颗子树如果子树中包含的技能出发点和技能到达点共ppp个,如果ppp是偶数的时候,那么这颗子树根节点的父亲边一定要走两次(可以画图帮助理解一下)而如果ppp是奇数的话,那么子树根节点的父亲边只需要走一次就好了.(画图帮助理解)
这就很简单了.
定义dp[i][j]dp[i][j]dp[i][j]表示以iii为根的子树,其子树中奇点个数为jjj,从iii点出发遍历完iii的子树再回到iii点,所需要的最小代价.
那么转移方程就是
∑p1p2...pmj(dp[vi][pi](![piamp;1]1)∗ci)→dp[u][j]\sum_{p_1p_2...p_mj}(dp[v_i][p_i](![p_i\amp;1]1)*c_i) \rightarrow dp[u][j]∑p1p2...pmj(dp[vi][pi](![pi1]1)∗ci)→dp[u][j]
∑p1p2...pmj(dp[vi][pi](![piamp;1]1)∗ci)→dp[u][j1]\sum_{p_1p_2...p_mj}(dp[v_i][p_i](![p_i\amp;1]1)*c_i) \rightarrow dp[u][j1]∑p1p2...pmj(dp[vi][pi](![pi1]1)∗ci)→dp[u][j1]
代码
#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::pairint,int pii;
const int N 1007;
std::vectorpii 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[ij],dp[u][i] dp[v][j] c);upd(tmp[ij1],dp[u][i] dp[v][j] c);}else {upd(tmp[ij],dp[u][i] dp[v][j] 2*c);upd(tmp[ij1],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
题解
首先我们将钓鱼的人按照xxx坐标排个序同时也记录一下他在答案里的顺序以便逆映射回去。 然后考虑每一条鱼能被哪些渔夫钓到也就是考虑贡献。我们能够很简单地知道一条鱼能够被钓到的地方在xxx轴上是一段连续的区间。当鱼的y坐标大于所给的线的长度时钓不到否则记鱼线长度大于yyy坐标的长度l−ydll - y dll−ydl能够钓到鱼区间即为[x−dl,xdl][x-dl, xdl][x−dl,xdl]。于是lower_bound和upper _bound找一下渔夫里面所对应的区间然后区间加单点查询。区间加单点查询这个操作在代码里是使用了差分数组来维护的最后算完之后把差分数组还原即可得到答案。 F.Min Max Convert
题解
大致的题意是给你两个长为nnn的数列A,BA,BA,B,然后你每次可以选择一段区间将区间覆盖成它的最大值或者是覆盖成它的最小值.要求输出一个长不超过2n2n2n的方案,将AAA数列变成BBB数列.
很明显的构造题.
我们首先要找一下规律以发现一些结论. 一个区间最多通过两次操作可以将区间覆盖为区间中任意一个数. 当vvv在区间边界上时,例如va[l]v a[l]va[l],将[l,r][l,r][l,r]覆盖为vvv的方法是:判断a[l]a[l]a[l]和a[l1]a[l1]a[l1]的大小关系,如果a[l]gt;a[l1]a[l] gt; a[l1]a[l]a[l1],那么就将[l1,r][l1,r][l1,r]取最小值,再将[l,r][l,r][l,r]取最大值. 当vvv在[l,r][l,r][l,r]中间时,可以将区间分成两段,分别操作. 对于BBB数列的每个数,在AAA数列中都应该有一个数与它对应.并且这些对应关系不交叉. 比如: A:5,3,1,2,2,4,7,6,8,6A:5,3,1,2,2,4,7,6,8,6A:5,3,1,2,2,4,7,6,8,6 B:1,1,2,4,4,7,7,8,8,8B:1,1,2,4,4,7,7,8,8,8B:1,1,2,4,4,7,7,8,8,8 那么对应关系是这样的: 好难讲,直接看我代码吧.
代码
#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[N1];int L[N1],R[N1];
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 n1) return 0*puts(-1);Loc[i] pos; }int p 1;rep(i,1,n) {if(Loc[i] ! Loc[i1]) {es[etot] (E){p,i,Loc[i]};p i1;}}for(int i etot-1;i 0;--i) {if(es[i].x es[i].b) {if(A[es[i].x] A[es[i].x1]) {Do(m,es[i].x1,es[i].e);Do(M,es[i].x,es[i].e);}if(A[es[i].x] A[es[i].x1]) {Do(M,es[i].x1,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].x1]) {Do(m,es[i].x1,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].x1]) {Do(M,es[i].x1,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
题解
队友LNCLNCLNC写的.
结论我们称依题目给出的公式计算矩阵AAA的得分时递归处理到的矩阵均称为AAA的“子矩阵”记这些矩阵中有nnn个为不“纯色”的矩阵则矩阵A的得分为4n14n14n1。
证明 用数学归纳法当AAA为1×11\times11×1的矩阵时显然结论成立。 假设A为2k×2k2^k\times2^k2k×2k的矩阵时结论成立现证A为2k1×2k12^{k1}\times2^{k1}2k1×2k1矩阵时结论仍成立
AAA纯色则其得分为1结论成立AAA不纯色记其四个子矩阵的不纯色的子矩阵个数分别为n1n_1n1、n2n_2n2、n3n_3n3和n4n_4n4则由假设它们的得分分别为4n114n_114n11、4n214n_214n21、4n314n_314n31和4n414n_414n41A中不纯色的子矩阵个数为n1n2n3n41n_1n_2n_3n_41n1n2n3n41由定义A的得分s5(n1n2n3n4)4(n1n2n3n41)1s5 (n_1n_2n_3n_4)4(n_1n_2n_3n_41)1s5(n1n2n3n4)4(n1n2n3n41)1结论成立。
综上结论得证。
考虑到一个矩阵为纯色则这个矩阵的每行需修改相同奇偶次且每列也需修改相同奇偶次统计有多少合法位置的连续2k2^k2k行与列修改的奇偶次数相同相乘结果即2k×2k2^k\times2^k2k×2k大小矩阵中纯色的个数求反面即可。这些区间形成了线段树的结构用线段树维护即可。
代码
#include bits/stdc.h
using namespace std;typedef long long ll;
const int maxn (120)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,o1,l,mid,deep1,x);else modify(id,o1|1,mid1,r,deep1,x);if(seg[id][o] ! -1) ans[id][deep]--;if(seg[id][o1] seg[id][o1|1]) seg[id][o] seg[id][o1];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%100;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][i1] ans[1][i1] (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
题解
第一步,根据图恢原来的排列.
在得到原来的排列以后,我们从排列中挑选一些位置(p1,p2,...pm)(p_1,p_2,...p_m)(p1,p2,...pm)组成一个独立支配集.必然有a[p1]lt;a[p2]lt;...lt;a[pm]a[p_1] lt; a[p_2] lt;... lt; a[p_m]a[p1]a[p2]...a[pm],只有这样,集合里的点之间才没有边相连,并且还要满足条件即[pi,pi1][p_i,p_{i1}][pi,pi1]之间的数要么大于a[pi1]a[p_{i1}]a[pi1],要么小于a[i]a[i]a[i].
并且在排列中不可能存在p0lt;p1并且a[p0]lt;a[p1]p_0 lt; p_1并且a[p_0] lt; a[p_1 ]p0p1并且a[p0]a[p1],否则的话,它也应该存在于集合当中,应为它与集合中的所有点都无边相连.同理,不存在pm1gt;pmp_{m1} gt; p_mpm1pm,使得a[pm1]gt;a[pm]a[p_{m1}] gt; a[p_m]a[pm1]a[pm].
如果plt;q且a[p]lt;a[q]且a[p,q]plt;q且a[p] lt; a[q]且a[p,q]pq且a[p]a[q]且a[p,q]之间的数不会存在介于a[p]a[p]a[p]与a[q]a[q]a[q]之间的数,就从ppp向qqq连边.
答案就是从入度为000的点,跑到出度为000的点的路径数之和.
拓扑序dp一下结束.
代码
#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];
vectorint 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);cinnm;for(int i 0;i m;i){int u,v;cinuv;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 i1;j n;j){if(vis[i][j]) continue;G[i].push_back(j);in[j];}}queueint 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 i1;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);coutansendl;return 0;
}J.Rabbit vs Turtle
题解
留坑 K.Points and Rectangles
题解
cdqcdqcdq分治的一道比较裸的题.
像这种能用二维线段树做的题(空间爆炸)都可以转换成离线cdq分治去解决.
每个点算作111个eventeventevent.
每个矩形按照左边和右边拆成两个eventeventevent,每个eventeventevent包含上下边界.
我们考虑单独对点和矩形算贡献. 对矩形算贡献: 所有在该矩形前加的点都对矩形的左边eventeventevent有111个负的影响,对矩形的右边eventeventevent有111个正的贡献. 维护一个树状数组,iii位置的值代表目前存在的点yyy值为iii的有多少个. 那么对于每一个分治过程按照eventeventevent的xxx从小到大的过程扫过来,遇见矩形左边eventeventevent就将贡献减去sum[down,up]sum[down,up]sum[down,up],遇见矩形右边eventeventevent,就将贡献加上sum[down,up]sum[down,up]sum[down,up]. 需要注意的一点是当多个eventeventevent的xxx相同的情况下,我们按照矩形左边eventeventevent,点eventeventevent,矩形右边eventeventevent 顺序扫. 对点算贡献. 矩形的左边eventeventevent对点会产生正的贡献,而矩形的右边eventeventevent会对点产生负的贡献. 还是按照eventeventevent的xxx值从小到大的过程扫过来,遇见矩形左边eventeventevent就将新树状数组的downdowndown位置111,将up1up1up1位置−1-1−1. 遇见矩形右边eventeventevent就将新树状数组的downdowndown位置−1-1−1,将up1up1up1位置111. 在遇见点eventeventevent时候,直接统计sum[0,y]sum[0,y]sum[0,y]的值就是包含这个点的矩形的贡献. 需要注意的一点是当多个eventeventevent的xxx相同的情况下,我们按照矩形左边eventeventevent,点eventeventevent,矩形右边eventeventevent 顺序扫.
代码
#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 tp0,int id0,int x0,int up0,int down0):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[N1];
int tot;int a[N],ans[N];
int bit1[N],bit2[N];
int ec 0,q;event tmp[N1];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(mid1,r);std::vectorint vec1,vec2;int s 0,p l,q mid1;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].up1,-1);vec2.push_back(es[p].down);vec2.push_back(es[p].up1);}else if(es[p].tp 2) {add(bit2,es[p].down,-1);add(bit2,es[p].up1,1);vec2.push_back(es[p].down);vec2.push_back(es[p].up1);}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;x2,y2;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;_a2,_b2,_c2,_d2;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,aec);ec std::unique(a,aec)-a;for(int i 0;i tot;i) {es[i].x std::lower_bound(a,aec,es[i].x)-a;es[i].up std::lower_bound(a,aec,es[i].up)-a;es[i].down std::lower_bound(a,aec,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;
}
