当前位置：首页 > news >正文

nflsoi 8.14 题解

news 2025/8/16 5:23:17

~~如果我好好写 dijkstra~~

怎么连放三道计数题？

C.#16441 三色骨牌 / AT_arc081_b Coloring Dominoes

题意

Snuke 有一个 $2 \times N$ 的矩阵，以及 $N$ 个多米诺骨牌，每一个骨牌是 $1 \times 2$ 或者 $2 \times 1$ 的。

现在 Snuke 决定用红色、浅蓝色和绿色三种颜色来绘制这些骨牌，要保证每一个骨牌与其周围相邻的骨牌颜色都不一样。

问一共有多少种不同的方案，答案对 $10^9+7$ 取模。

每一个骨牌都会用一个英文字母表示，保证每一个骨牌的字母都不一样。

思路

首先不可能出现出现错位的 $2×12\times 1$ 骨牌，因此对于同一个 $i$ ， $a_{1,i}$ 和 $a_{2,i}$ 上放置的骨牌类型相同。因此不难预处理，每列 $i$ 上放的骨牌种类。钦定 $1$ 类为 $1×21\times 2$ 、 $2$ 类为 $2×12\times1$ 。

考虑根据第 $i$ 列判断 $i + 1$ 列的方案数：

首先特判第 $1$ 列的种类，是 $1$ 类就有 $3$ 中方案； $2$ 类因为堆叠了上下两张牌，于是是 $3×2=63\times 2=6$ ；
如果 $i$ 列放 $1$ ， $i + 1$ 列也放 $1$ ，那么后者有 $2$ 种颜色可以选；
如果 $i$ 列放 $1$ ， $i + 1$ 列放了 $2$ （即 $i + 2$ 列也放了 $2$ ），那么上下两个分别能涂 $2$ 种、 $1$ 种，即 $2×1=22\times 1=2$ ；
如果 $i$ 列放 $2$ ， $i + 1$ 列也放了 $2$ ，且 $i$ 列和 $i + 1$ 列分属不同的两对 $2×12\times 1$ ，那么有 $3$ 种染色方案：

注意要跳到两张牌的分界。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=56,mod=1e9+7;
ll n;
char a[3][N];
ll col[N];
int main()
{scanf("%lld",&n);for(int i=1;i<=2;i++){for(int j=1;j<=n;j++)cin>>a[i][j];}for(int i=1;i<=n;i++){if(a[1][i]==a[2][i])col[i]=1;else col[i]=col[i+1]=2,i++;}ll ans=3;if(col[1]==2)ans=ans*2%mod;for(int i=1;i<n;i++)//i+1填 {if(col[i]==1&&col[i+1]==1)ans=ans*2%mod;//2if(col[i]==1&&col[i+1]==2)ans=ans*2%mod;//2*1if(i>1&&col[i]==2&&col[i+1]==2)ans=ans*3%mod;//1|3 2 2//2|1 1 3if(col[i+1]==2){i++;continue;}//+2跳到2*1末尾 }printf("%lld",ans);return 0;
}

D.#4758 翻转行列 / BZOJ4705 棋盘游戏

狐狸次郎有一个由 $n$ 行 $m$ 列组成的矩形网格。最初，网格中的每个单元格都包含字符 0。

行翻转操作是指次郎选择网格的某一行，将该行中所有的 0 变为 1，所有的 1 变为 0。类似地，列翻转操作是指次郎对网格的某一列执行相同的操作。

次郎最初拥有一个所有单元格都是’0’的网格。他先进行了 $R co u n t$ 次行翻转操作，然后进行了 $C co u n t$ 次列翻转操作。（次郎可能对同一行或同一列进行多次翻转）最终，次郎发现网格中恰好有 $k$ 个 1。

我们关注的是次郎进行行和列翻转操作的不同方式的数量。如果某一行或某一列被翻转的次数不同，则认为是不同的翻转方式。（即行和列的翻转顺序不影响结果。）

结果对 $555555555$ 取模。

$1≤n,m≤15551\le n,m\le 1555$ ， $0≤Rcount,Ccount≤15550\le Rcount,Ccount\le 1555$ 。

思路

根据容斥原理，对行做 $r$ 次操作、列做 $c$ 次操作（不操作在同一行或者列上），最终棋盘上有 $r m + c n - 2 rc$ 个 1。因此不难 $O(rc×cc)O(rc\times cc)$ 求出所有 $k = r m + c n - 2 rc$ 的 $(r, c)$ ，其中 $0≤r≤rc,0≤c≤cc0\le r\le rc,0\le c\le cc$ ，如果没有可行解就是无解。

统计方案数，对于一组解 $(r, c)$ ，先选定必须操作行列 $(nr)(mc)\dbinom{n}{r}\dbinom{m}{c}$ 。我们发现还有剩余次数，考虑两次两次地做到重复的行或者列上。

先判断 $rc - r$ 和 $cc - c$ 是否为偶数，如果其一为奇数都会剩下一次操作无法安置，此时 $(r, c)$ 。否则，就考虑把 $rc−r2\dfrac{rc-r}{2}$ 对操作分到 $n$ 行、 $cc−c2\dfrac{cc-c}{2}$ 分到 $m$ 列，这就相当于把 $rc−r2\dfrac{rc-r}{2}$ 拆成 $n$ 个数的和，数可以为 $0$ ，经典的插板法（辅助板）问题！

具体细节见代码：

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define mk make_pair
#define fi first
#define se second
const ll N=3555,mod=555555555;
ll n,m,rc,cc,k;
vector<pll>rot;
ll C[N][N];
void init()
{for(int i=0;i<N;i++)C[i][0]=C[i][i]=1;for(int i=1;i<N;i++){for(int j=1;j<i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;}
}
int main()
{scanf("%lld%lld%lld%lld%lld",&n,&m,&rc,&cc,&k);init();for(int r=0;r<=rc;r++){for(int c=0;c<=cc;c++){if(k==r*m+c*n-2*c*r){//	printf("%lld=%lld*%lld+%lld*%lld-%lld*%lld\n",k,r,m,c,n,c,r);rot.push_back(mk(r,c));}}}if(!rot.size()){puts("0");return 0;}ll ans=0;for(auto x:rot){ll r=x.fi,c=x.se;ll ret=C[n][r]*C[m][c]%mod;if(((rc-r)&1)||((cc-c)&1))continue;ll t1=(rc-r)/2,t2=(cc-c)/2;if(t1)ret=ret*C[t1+n-1][n-1]%mod;if(t2)ret=ret*C[t2+m-1][m-1]%mod;ans=(ans+ret)%mod;}printf("%lld",ans);return 0;
}

E.#4758 键帽

题意

一个字符串成为好串，仅当不出现大于 $k$ 个连续的元音字母（a,e,i,o,u）。 $26$ 个元音字母，除了 $5$ 个元音之外，剩下 $21$ 种都是辅音字母。

给定 $T$ 组询问，询问长度为 $n$ 的好串有多少个，这些好串都不能出现大于 $k$ 个连续元音。

$1≤k<n≤1061\le k<n\le 10^6$ 。

思路

先想到的是最显然的 $f_{i,j}$ 表示第 $i$ 位结尾的字符串，连续了多少个元音字母。转移式很显然：
$fi,0=21∑j=0min⁡(k,i−1)fi−1,jfi,j=5fi−1,j−1,1≤j≤k\begin{matrix} f_{i,0}=21\displaystyle\sum_{j=0}^{\min(k,i-1)}f_{i-1,j}\\ f_{i,j}=5f_{i-1,j-1},1\le j\le k \end{matrix}$

然后答案是 $∑j=0kfn,j\displaystyle\sum_{j=0}^kf_{n,j}$ ？我赛时难道唐成这样？50pts 的简单暴力都差点没拿下？

考虑优化，我们发现状态开不下，但是其实多少个连续元音结尾可以先枚举，于是状态改为 $f_{i,op}$ 表示第 $i$ 为辅音（ $o p = 0$ ）或者元音（ $o p = 1$ ）的方案数。转移其实还是 $O (nk)$ ，我们考虑枚举转移点 $j$ ， $j$ 填辅音，然后 $j+1∼ij+1\sim i$ 全部元音；不过已经优化了空间，也为我们的优化提供了思路。
$fi,0=21(fi−1,0+fi−1,1)fi,1=∑j=max⁡(0,i−k)i−1fj,0×5i−j\begin{matrix} f_{i,0}=21(f_{i-1,0}+f_{i-1,1})\\ f_{i,1}=\displaystyle\sum_{j=\max(0,i-k)}^{i-1} f_{j,0}\times5^{i-j} \end{matrix}$

答案是 $f_{n,0}+f_{n,1}$ 。

for(int i=1;i<=n;i++)
{f[i][0]=(f[i-1][0]+f[i-1][1])%mod*21%mod;ll p=5,s=0;for(int j=i-1;j>=max(0ll,i-k);j--){f[i][1]=(f[i][1]+f[j][0]*p%mod)%mod;s=(s+f[j][0]*p%mod)%mod;p=p*5%mod;}
}

观察转移式，我们发现，第二条式子我们只需要知道 $i$ 前面 $k$ 个 $f_{j,0}$ 的信息，并且更巧的是，这些 $f_{j,0}$ 都要乘上 $5$ 的幂次 $5^{i-j}$ 。这让人联想到哈希了。

考虑用哈希维护 $k$ 个 $fj,0×5i−jf_{j,0}\times 5^{i-j}$ 的和，信息合并到 $f_{i,1}$ ，并且更新完当前的 $f_{i,0}$ 后，我们考虑将 $f_{i,0}$ 加入哈希值。

当哈希值维护的信息小于 $k$ 个（注意 $j = 0$ 也算一个），即 $i < k$ 时，就 $×5\times 5$ 移位然后加进去，否则就把先头那一位去掉，再移位加数。

$O (n)$ 做完。多测记得清空，记得勤取模。

（其实就是根据暴力强制优化而已）

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+5,mod=1e9+7;
ll Q,n,k;
ll pw[N];
ll f[N][2];//0辅1元
void init()
{pw[0]=1;for(int i=1;i<N;i++)pw[i]=pw[i-1]*5%mod;
}
int main()
{scanf("%lld",&Q);init();while(Q--){ll n,k;scanf("%lld%lld",&n,&k);f[0][0]=1;ll tem=5;for(int i=1;i<=n;i++){f[i][0]=(f[i-1][0]+f[i-1][1])%mod*21%mod;/*	ll p=5,s=0;for(int j=i-1;j>=max(0ll,i-k);j--){f[i][1]=(f[i][1]+f[j][0]*p%mod)%mod;s=(s+f[j][0]*p%mod)%mod;p=p*5%mod;}*///	cout<<i<<" "<<tem<<" "<<s<<endl;f[i][1]=(f[i][1]+tem)%mod;tem=(tem+f[i][0])%mod*5%mod;if(i>=k)tem=(tem-pw[k+1]*f[i-k][0]%mod+mod)%mod;}printf("%lld\n",(f[n][0]+f[n][1])%mod);for(int i=0;i<=n;i++)f[i][0]=f[i][1]=0;}return 0;
}
/*
5
2000 1000
1998 332
555 314
423 122
1888 11 
20 10
*/

F.#4557 偷金计划 / 洛谷 P8240 偷铀计划

题意

你是一个小偷，你决定偷点铀来让自己在 Digdig.io 游戏中能够迅速变大。

你有一张地图，这个矿洞是一张 $n$ 个点 $m$ 条边的无向图。有 $K$ 个守卫保护着矿洞的安全，第 $i$ 个守卫守在第 $P_i$ 个点上。

你偷了 $x$ 千克铀，准备选一条路径从 $S$ 点转移到 $T$ 点。如果 $x > 0$ ，那么在转移过程中，你需要保证在任意时刻与每个守卫的距离都大于 $x$ 。不然就会被发现！

显然，你不会只偷一次，你需要偷 $Q$ 次铀，每次给定 $S$ 和 $T$ ，询问你最多能偷多少千克的铀。

$1≤n,K,Q≤1051\leq n,K,Q\leq 10^5$ ， $1≤m≤2×1051\leq m\leq 2\times 10^5$ ， $1≤x,y,Pi≤n1\leq x,y,P_i\leq n$ ， $1≤z≤1091\leq z\leq 10^9$ 。

思路

拼好题哈哈。

我们尽量走那些，两端点离守卫尽量远的边。这怎么那么像 P1967 货车运输呢？其方法是把最大的边搞下来做最大生成树，然后查询的时候，找两点的 lca，维护倍增数组（父亲以及最小值）。

我们发现和守卫的距离是针对点的而不针对边。我们可以 dijkstra 来预处理出 $dis_u$ 表示，距离 $u$ 最近的守卫距其距离。其实就是把每个守卫都推进优先队列，反正 dijkstra 实现的本质就是 bfs。（是谁赛时 dijkstra 写假了鸭 qwq）

预处理出 $dis_u$ ，对于 $(u, v)$ ，将边权 $w$ 设为 $min(dis_u,dis_v)$ ， $w$ 就是拿着铀走过这条边的上限。对于询问从 $u→vu\to v$ 的路径上能取到最多多少千克的油，就是求一条能使路径上上限最小值最大的路径。此时就是裸的货车运输了。

于是拿 kruskal 跑一颗最大生成树，在树上面预处理 lca；为了得到路径上的最小边权，我们类似地维护 $mi_{u,i}$ 表示， $u$ 到其 $2_i$ 级祖先路径上的最小边权。然后求 lca 时，同时合并 $mi_{x/y,i}$ 。

最后答案要 $- 1$ ，因为要求不能大于，记得别减到 $- 1$ 了，和 $0$ 取 $max⁡\max$ 。

本做法支持在线，时间复杂度 $O(mlog⁡n+mlog⁡m+qlog⁡n)O(m\log n+m\log m+q\log n)$ ，分别是 dijkstra、kruskal 和在线 lca 的复杂度，在洛谷和 nflsoj 都跑得挺快的。

这题的做法还有很多，有把询问带到最大生成树合并那里启发式合并的，还有整体二分（这题二分的特征很明显，机房大佬都是一眼顶针，~~而我却不会整体二分~~，不过多一个 $log⁡\log$ ）、kruskal 重构树等。

（这一题也启示我要复习基础算法）

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+9,M=2e5+9;
const ll inf=6e14;
int n,m,k,Q;
ll dis[N];
struct bian
{int u,v;ll dist;
}b[M];
bool cmp(bian x,bian y)
{return x.dist>y.dist;
}
int fa[N];
int fz(int x)
{while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;
}
struct edge
{int to,next;ll w;
}e[M<<1],e1[M<<1];
int idx,head[M];
void addedge(int u,int v,ll w)
{idx++;e[idx].to=v;e[idx].next=head[u];e[idx].w=w;head[u]=idx;
}
struct node
{ll val;int id;
};
bool operator < (node x,node y)
{return x.val>y.val;
}
bool vis[N];
priority_queue<node>q;
void dijkstra()
{while(!q.empty()){node tem=q.top();q.pop();int u=tem.id;if(vis[u])continue;vis[u]=1;for(int i=head[u];i;i=e[i].next){int v=e[i].to;ll w=e[i].w;if(dis[u]+w<dis[v]){dis[v]=dis[u]+w;q.push((node){dis[v],v});}}}
}
int idy,heay[M];
void addedge1(int u,int v,ll w)
{idy++;e1[idy].to=v;e1[idy].next=heay[u];e1[idy].w=w;heay[u]=idy;
}
void kruskal()
{for(int i=1;i<=m;i++){int fu=fz(b[i].u),fv=fz(b[i].v);if(fu==fv)continue;fa[fv]=fu;addedge1(b[i].u,b[i].v,b[i].dist);addedge1(b[i].v,b[i].u,b[i].dist);//	cout<<b[i].u<<" "<<b[i].v<<" "<<b[i].dist<<endl;cnt++;if(cnt==n-1)break;}
}
ll f[N][20],dep[N],mi[N][20];
void dfs(int u,int fa)
{if(fa==0){dep[u]=1;mi[u][0]=inf;}for(int i=heay[u];i;i=e1[i].next){int v=e1[i].to;ll w=e1[i].w;if(v==fa)continue;dep[v]=dep[u]+1;f[v][0]=u;mi[v][0]=w;for(int j=1;(1<<j)<=dep[v];j++){f[v][j]=f[f[v][j-1]][j-1];mi[v][j]=min(mi[v][j-1],mi[f[v][j-1]][j-1]);}dfs(v,u);}
}
ll lca(int x,int y)
{ll ret=inf;if(dep[x]<dep[y])swap(x,y);for(int i=19;i>=0;i--)if(dep[x]-(1<<i)>=dep[y])ret=min(ret,mi[x][i]),x=f[x][i];if(x==y)return ret;for(int i=19;i>=0;i--){if(f[x][i]!=f[y][i]){ret=min(ret,min(mi[x][i],mi[y][i]));x=f[x][i];y=f[y][i];}}ret=min(ret,min(mi[x][0],mi[y][0]));return ret;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int u,v;ll w;scanf("%d%d%lld",&u,&v,&w);addedge(u,v,w);addedge(v,u,w);b[i]=(bian){u,v,w};}for(int i=1;i<=n;i++)dis[i]=inf;scanf("%d",&k);for(int i=1;i<=k;i++){int u;scanf("%d",&u);dis[u]=0;q.push((node){0,u});}dijkstra();
//	for(int i=1;i<=n;i++)
//	cout<<dis[i]<<" ";
//	cout<<endl;//	cout<<"check\n";for(int i=1;i<=m;i++)b[i].dist=min(dis[b[i].u],dis[b[i].v]);
//	for(int i=1;i<=m;i++)
//	cout<<b[i].u<<" "<<b[i].v<<" "<<b[i].dist<<"\n";sort(b+1,b+m+1,cmp);int cnt=0;for(int i=1;i<=n;i++)fa[i]=i;
//	cout<<"scs\n";kruskal();dfs(1,0);scanf("%d",&Q);while(Q--){int u,v;scanf("%d%d",&u,&v);printf("%lld\n",max(0ll,lca(u,v)-1));}return 0;
}

G.#7488 高速公路 / BZOJ3488 3488 ONTAK2010 Highways

题意

Byteland 是一个小国，其城市通过 $n - 1$ 条双向道路连接。从每个城市到其他任何城市都只有一条路径可走（即构成一棵树），这导致了严重的交通拥堵。为此，该国修建了 $m$ 条高速公路，每条高速公路连接着一对城市。

路径指的是由道路和/或高速公路组成的序列，且路径上的所有城市都必须是不同的；
对于任意一对城市 $x, y$ ，存在且仅存在一条不使用任何高速公路的路径，我们称这条路径为 $x$ 到 $y$ 的主路径（即树上 $x$ 到 $y$ 的唯一路径）；
人们从城市 $x$ 到城市 $y$ 时，要么选择主路径，要么使用一些高速公路。在后一种情况下，路径除了 $x$ 和 $y$ 之外，不能与主路径有任何交集，且必须恰好包含一条高速公路。

你的任务是计算给定的多对城市之间，满足上述条件的路径数量。

思路

神仙转化题。而且有两个很经典的 trick。

能走高速公路的路径有两种情况：
在这里插入图片描述

$u$ 和 $v$ 分属同子树的两支，此时高速公路要一边在 $u$ 子树内，一边在 $v$ 的子树内（如左图）；
$u$ 和 $v$ 存在多级祖先关系，那么告诉公路不能再 $u→vu\to v$ 的链上，需一边在 $u$ 子树内，一边在 $v$ 的子树外、或者遍历 $z$ （为 $u→vu\to v$ 链上的 $son_v$ ）之前的 $v$ 子树、或者 $z$ 之后的 $v$ 子树（如右图）。

有一个经典的 trick，子树存在性问题，转化为一个点 $x$ 的 $dfn_x$ 存在于 $L_u,R_u]$ ， $L, R$ 表示入和出 dfs 序。

于是我们将每个询问 $(u, v)$ 像如上分类，处理出限定高速公路起点 $x$ 和终点 $y$ 的两个区间：

$x∈[Lu,Ru],y∈[Lv,Rv]x\in[L_u,R_u],y\in[L_v,R_v]$ ；
$x∈[Lu,Ru],y∈[1,Lz)∪(Rz,max⁡dfn]x\in[L_u,R_u],y\in[1,L_z)\cup(R_z,\max dfn]$

这又是一个经典问题——二维数点，我们发现 $x$ 和 $y$ 的限制并不相关，于是变成两个维度：
在这里插入图片描述

把告诉公路 $x↔yx\leftrightarrow y$ 看作点对 $dfn_x,dfn_y)$ （或 $dfn_y,dfn_x)$ ，一次只可能满足一个，因此不会算重）即计算子矩形内有多少高速公路点，可以对 $x$ 轴排序扔上树状数组或者 cdq 分治，拆成 $4$ 个询问去做。（这里选择前者）

对于第二个限制，虽然条件变多了，也只是变成了两个矩形（因为是用 $∪\cup$ 连接的，两个矩形可以同时存在），拆成 $8$ 个询问。

代码

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#pragma GCC optimise(2)
#pragma GCC optimise(3,"Ofast","inline")
inline int read()
{int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
const int N=1e5+9,M=5e5+9;
int n,m,Q;
vector<int>G[N];
int dfn[N],ti,L[N],R[N],dep[N];
int f[N][19];
void dfs(int u,int fa)
{dep[u]=dep[fa]+1;f[u][0]=fa;for(int i=1;(1<<i)<=dep[u];i++)f[u][i]=f[f[u][i-1]][i-1];dfn[u]=++ti;L[u]=ti;for(auto v:G[u]){if(v==fa)continue;dfs(v,u);}R[u]=ti;
}
int jump(int x,int y)//在y下一深度 
{for(int i=18;i>=0;i--)if(dep[x]-(1<<i)>=dep[y]+1)x=f[x][i];return x;
}
int tot;
struct hwy
{int l,r;
}h[N<<1];
bool cmp1(hwy x,hwy y)
{return x.l<y.l;
}
struct que
{int l,r,val,id;
}q[M*10];
bool cmp2(que x,que y)
{return x.l<y.l; 
}
struct BT
{int T[N];int lowbit(int x){return x&(-x);}void add(int x,int k){for(int i=x;i<=n+1;i+=lowbit(i))T[i]+=k;}int query(int x){int ret=0;for(int i=x;i>=1;i-=lowbit(i))ret+=T[i];return ret;}
}B;
int ans[M];
int main()
{n=read();for(int i=1;i<n;i++){int u,v;u=read(),v=read();G[u].push_back(v);G[v].push_back(u);}dfs(1,0);m=read();for(int i=1;i<=m;i++){int u,v;u=read(),v=read();h[i*2-1]=(hwy){dfn[u],dfn[v]};h[i*2]=(hwy){dfn[v],dfn[u]};}Q=read();for(int i=1;i<=Q;i++){int u,v;u=read(),v=read();if(dep[u]<dep[v])swap(u,v);//u下 int dw=jump(u,v);//	cout<<dw<<endl;if(dep[u]!=dep[v]&&f[dw][0]==v){//左端in[L[u],R[u]]且右端in[1,L[dw])∩(R[dw],n] 不能取到dw否则要经过路径 /*	q[++tot]=(que){L[u]-1,L[dw]-1,-1,i};q[++tot]=(que){L[u]-1,R[dw],1,i};q[++tot]=(que){R[u],L[dw]-1,1,i};q[++tot]=(que){R[u],R[dw],-1,i};q[++tot]=(que){L[u]-1,n,-1,i};q[++tot]=(que){R[u],n,1,i};*/q[++tot]=(que){L[u]-1,0,1,i};q[++tot]=(que){L[u]-1,L[dw]-1,-1,i};q[++tot]=(que){R[u],0,-1,i};q[++tot]=(que){R[u],L[dw]-1,1,i};q[++tot]=(que){L[u]-1,R[dw],1,i};q[++tot]=(que){L[u]-1,n,-1,i};q[++tot]=(que){R[u],R[dw],-1,i};q[++tot]=(que){R[u],n,1,i};}else {//左端in[L[u],R[u]]且右端in[L[v],R[v]]//即(L[u],L[v])-(R[u],R[v])的矩形内有多少高速公路 q[++tot]=(que){L[u]-1,L[v]-1,1,i};q[++tot]=(que){L[u]-1,R[v],-1,i};q[++tot]=(que){R[u],L[v]-1,-1,i};q[++tot]=(que){R[u],R[v],1,i};}}sort(h+1,h+2*m+1,cmp1);sort(q+1,q+tot+1,cmp2);int pos=1;for(int i=1;i<=tot;i++){while(pos<=2*m&&h[pos].l<=q[i].l)B.add(h[pos].r+1,1),pos++;ans[q[i].id]+=q[i].val*B.query(q[i].r+1);}for(int i=1;i<=Q;i++)printf("%d\n",ans[i]+1);return 0;
}