#3
Buying Sets
题面
非常典型的最小割板子题呢。
将集合和元素看成是一一匹配，变成了最小割最经典的二分图匹配问题了。从 \(s\) 向集合 \(i\) 连边，割掉表示不选 \(i\) 集合，从元素 \(i\) 向 \(t\) 连边，割掉表示选择元素 \(i\)。问题就变成了如何赋边权，使得满足条件。可以发现答案=权值总和-不选的集合的权值和，将所有权值取反，此时就是要求不选的集合的权值和的最小值。因为是求匹配，所以最少会割 \(n\) 条边，为了限制割的边更多，可以将所有边都加上 \(inf(inf\text{为一个超过集合权值和的极大数})\)，此时如果多割一条边，便不是最小割了。不选的集合的权值和的最小值即为最小割减去 \(inf\times n\) 即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=310,inf=1e9;
int S,T,n,cnt,tot=1,head[N<<1];
struct edge{
int v,w,nxt;
}e[N*N*2];
void add(int u,int v,int w){
e[++tot].v=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
}
void add_e(int u,int v,int w){
add(u,v,w);
add(v,u,0);
}
namespace Max_Flow{
int cur[N<<1],dep[N<<1];
bool bfs(){
queue<int>q;
for(int i=1;i<=T;i++){
dep[i]=0;
}
dep[S]=1;
q.push(S);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(!dep[v]&&w){
dep[v]=dep[u]+1;
if(v==T){
return 1;
}
q.push(v);
}
}
}
return 0;
}
int dfs(int u,int flow){
if(u==T){
return flow;
}
int ans=0;
for(int i=cur[u];i;i=e[i].nxt){
cur[u]=i;
int v=e[i].v,w=e[i].w;
if(dep[v]==dep[u]+1&&w){
int res=dfs(v,min(flow,w));
e[i].w-=res;
e[i^1].w+=res;
flow-=res;
ans+=res;
}
if(!flow){
break;
}
}
if(!ans){
dep[u]=0;
}
return ans;
}
int dinic(){
int ans=0;
while(bfs()){
for(int i=1;i<=T;i++){
cur[i]=head[i];
}
ans+=dfs(S,1e18);
}
return ans;
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n);
S=n*2+1,T=n*2+2;
for(int i=1;i<=n;i++){
read(cnt);
for(int j=1;j<=cnt;j++){
int x;
read(x);
add_e(i,x+n,inf);
}
}
int ans=0;
for(int i=1,x;i<=n;i++){
read(x);
ans-=x;
add_e(S,i,inf-x);
add_e(i+n,T,inf);
}
ans-=Max_Flow::dinic()-n*inf;
write_endl(-ans);
// cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
Good Graph
题面
因为环的异或和为一，如果存在环套环，两个合法的环异或出来的新环异或值一定为 \(0\)，所以不存在环套环，即连通块为仙人掌。
在线显然是lct干的事情，我们考虑离线。可以发现环的最后一条边我们是无法判断是否需要加入的，于是我们可以先求出树，非树边 \((u,v,w)\) 合法的条件为路径 \(u\rightarrow v\) 上的边没有在任何环中，且 \(dis_u\oplus dis_v\oplus w=1\)，其中 \(dis_x\) 表示点 \(x\) 到 \(x\) 所在生成树的根的路径异或和。树剖后用线段树维护一下即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=5e5+10;
int n,m,dsu[N],ans[N];
struct edge{
int u,v,w;
}e[N];
vector<pii>G[N];
int getfa(int x){
if(dsu[x]!=x){
dsu[x]=getfa(dsu[x]);
}
return dsu[x];
}
int id[N],idx,top[N],fa[N],heavy[N],siz[N],dep[N],dis[N];
void make_tree(int u,int father){
fa[u]=father;
dep[u]=dep[father]+1;
siz[u]=1;
for(auto x:G[u]){
int v=x.first,w=x.second;
if(v==father){
continue;
}
dis[v]=dis[u]^w;
make_tree(v,u);
siz[u]+=siz[v];
if(siz[heavy[u]]<siz[v]){
heavy[u]=v;
}
}
}
void dfs(int u,int topf){
id[u]=++idx;
top[u]=topf;
if(heavy[u]){
dfs(heavy[u],topf);
}
for(auto x:G[u]){
int v=x.first;
if(v==fa[u]||v==heavy[u]){
continue;
}
dfs(v,v);
}
}
namespace Seg_Tree{
int mx[N<<2],tag[N<<2];
int ls(int p){
return p<<1;
}
int rs(int p){
return p<<1|1;
}
void push_up(int p){
mx[p]=max(mx[ls(p)],mx[rs(p)]);
}
void push_down(int p){
if(tag[p]){
mx[ls(p)]=mx[rs(p)]=tag[ls(p)]=tag[rs(p)]=1;
}
}
void update(int p,int l,int r,int q_l,int q_r){
if(q_l<=l&&r<=q_r){
mx[p]=tag[p]=1;
return;
}
int mid=(l+r)>>1;
if(q_l<=mid){
update(ls(p),l,mid,q_l,q_r);
}
if(q_r>mid){
update(rs(p),mid+1,r,q_l,q_r);
}
push_up(p);
}
int query(int p,int l,int r,int q_l,int q_r){
if(q_l<=l&&r<=q_r){
return mx[p];
}
int res=0,mid=(l+r)>>1;
push_down(p);
if(q_l<=mid){
res=max(res,query(ls(p),l,mid,q_l,q_r));
}
if(q_r>mid){
res=max(res,query(rs(p),mid+1,r,q_l,q_r));
}
return res;
}
}
int query(int u,int v){
int res=0,flag=(u==2&&v==4);
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
res=max(res,Seg_Tree::query(1,1,n,id[top[u]],id[u]));
u=fa[top[u]];
}
if(dep[u]>dep[v]){
swap(u,v);
}
if(u!=v){
res=max(res,Seg_Tree::query(1,1,n,id[u]+1,id[v]));
}
return res;
}
void update(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
Seg_Tree::update(1,1,n,id[top[u]],id[u]);
u=fa[top[u]];
}
if(dep[u]>dep[v]){
swap(u,v);
}
if(u!=v){
Seg_Tree::update(1,1,n,id[u]+1,id[v]);
}
}
void solve(){
read(n),read(m);
for(int i=1;i<=n;i++){
dsu[i]=i;
}
for(int i=1;i<=m;i++){
read(e[i].u),read(e[i].v),read(e[i].w);
}
for(int i=1;i<=m;i++){
int u=getfa(e[i].u),v=getfa(e[i].v);
if(u!=v){
dsu[v]=u;
ans[i]=1;
G[e[i].u].pb(mp(e[i].v,e[i].w));
G[e[i].v].pb(mp(e[i].u,e[i].w));
}
}
for(int i=1;i<=n;i++){
if(!id[i]){
make_tree(i,0);
dfs(i,i);
}
}
for(int i=1;i<=m;i++){
if(!ans[i]){
if(dis[e[i].u]^dis[e[i].v]^e[i].w!=1){
continue;
}
int mx=0;
if(query(e[i].u,e[i].v)){
continue;
}
update(e[i].u,e[i].v);
ans[i]=1;
}
}
for(int i=1;i<=m;i++){
if(ans[i]){
puts("YES");
}
else{
puts("NO");
}
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
Phoenix and Earthquake
题面
这里先给出结论，只要点权和大于 \((n-1)\times x\) 且图联通，任意一棵生成树均可以满足条件。
证明：考虑归纳法，假设我们已经处理完了 \(u\) 的子树，此时 \(u\) 点权值为 \(a_u\)，剩下部分权值和为 \(sum\)，分类讨论。
- \(a_u\ge x\)，此时可以直接将其与父节点合并，没有影响。
- \(a_u < x\)，此时去掉该点剩下的部分会满足条件，这题边最后合并即可。
实现过程直接根据上述证明过程实现即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=3e5+10;
int n,m,val,a[N],sum,tot=1,head[N],vis[N],ans[N],l=0,r;
struct edge{
int u,v,nxt,id;
}e[N<<1];
void add(int u,int v,int id){
e[++tot].v=v;
e[tot].u=u;
e[tot].nxt=head[u];
e[tot].id=id;
head[u]=tot;
}
void add_e(int u,int v,int id){
add(u,v,id);
add(v,u,id);
}
void dfs(int u,int from){
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(vis[v]){
continue;
}
dfs(v,i);
}
if(u==1){
return;
}
if(a[u]>=val){
a[e[from].u]+=a[u]-val;
ans[++l]=e[from].id;
}
else{
ans[--r]=e[from].id;
}
}
void solve(){
read(n),read(m),read(val);
l=0,r=n;
for(int i=1;i<=n;i++){
read(a[i]);
sum+=a[i];
}
if(sum<(n-1)*val){
puts("NO");
return;
}
for(int i=1,u,v;i<=m;i++){
read(u),read(v);
add_e(u,v,i);
}
dfs(1,0);
for(int i=1;i<=n;i++){
if(!vis[i]){
puts("NO");
return;
}
}
puts("YES");
for(int i=1;i<n;i++){
write_endl(ans[i]);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[COCI 2021.11]嫌疑人
题面
也是一道结论题，先给出结论吧，但这个不会证，等会了再补。每次选择会选区间内最长的线段不交的子区间。
求证的部分类似于Minimal Segment Cover ，可以用倍增维护进行 \(2^j\) 次操作后，以 \(i\) 为起点能到达的最远的位置，询问时倍增跳即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=4e5+10,Lg=20;
int n,pos[N],q[N][Lg+5];
struct node{
int l,r;
}seg[N];
namespace Seg_Tree{
int ans[N<<2],tag[N<<2];
int ls(int p){
return p<<1;
}
int rs(int p){
return p<<1|1;
}
void push_down(int p){
ans[ls(p)]+=tag[p];
ans[rs(p)]+=tag[p];
tag[ls(p)]+=tag[p];
tag[rs(p)]+=tag[p];
tag[p]=0;
}
void push_up(int p){
ans[p]=max(ans[ls(p)],ans[rs(p)]);
}
void update(int p,int l,int r,int q_l,int q_r,int val){
if(q_l<=l&&r<=q_r){
ans[p]+=val;
tag[p]+=val;
return;
}
int mid=(l+r)>>1;
push_down(p);
if(q_l<=mid){
update(ls(p),l,mid,q_l,q_r,val);
}
if(q_r>mid){
update(rs(p),mid+1,r,q_l,q_r,val);
}
push_up(p);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n);
for(int i=1;i<=n;i++){
read(seg[i].l),read(seg[i].r);
pos[i*2-1]=seg[i].l;
pos[i*2]=seg[i].r;
}
sort(pos+1,pos+2*n+1);
int cnt=unique(pos+1,pos+n*2+1)-pos-1;
for(int i=1;i<=n;i++){
seg[i].l=lower_bound(pos+1,pos+cnt+1,seg[i].l)-pos;
seg[i].r=lower_bound(pos+1,pos+cnt+1,seg[i].r)-pos;
}
for(int i=n,last=n;i;i--){
Seg_Tree::update(1,1,cnt,seg[i].l,seg[i].r,1);
while(Seg_Tree::ans[1]>1&&last>=i){
Seg_Tree::update(1,1,cnt,seg[last].l,seg[last].r,-1);
last--;
}
q[i][0]=last;
}
for(int i=1;i<Lg;i++){
for(int j=1;j<=n;j++){
q[j][i]=q[q[j][i-1]+1][i-1];
if(!q[j][i]){
q[j][i]=n+1;
}
}
}
int s;
read(s);
while(s--){
int l,r,ans=0;
read(l),read(r);
for(int i=Lg-1;i>=0&&l<=r;i--){
if(q[l][i]<=r){
ans|=(1<<i);
l=q[l][i]+1;
}
}
if(l<=r){
ans++;
}
write_endl(ans);
}
// cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
「JOISC 2017 Day 1」港口设施
题面
将进入看作左括号，出去看作右括号，那么如果答案合法，两个栈最后的括号序列一定合法。，因此，如果两对括号代表的区间有交，则在代表两对括号的点之间连边，合法则图为二分图。但这样边很多，需要优化建图。
回到原来的括号序列，考虑从左到右连边，如果当前的是右括号，前面会有独立的左括号和带右括号的极大括号序列。单独的独立左括号直接连边即可，对于极大括号序列，可以只连第一个独立左括号，连边后发现，这样仍满足原来的要求。因为极大括号序列中包含第一个独立左括号的括号对向其连了边，且该括号对和当前括号对相互包含，之间不连边，而内部其它独立左括号都与包含括号连边，以此递推，这样连边是满足条件的。用并查集维护第一个独立左括号的位置，用 \(nxt\) 数组维护每个括号所属极长括号序列包含的括号。
点击查看代码
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO {
template<typename T>
inline void read(T &x) {
x = 0;
int f = 1;
char ch = getchar();
while (ch > '9' || ch < '0') {
if (ch == '-') {
f = -1;
}
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
x = (f == 1 ? x : -x);
}
template<typename T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x >= 10) {
write(x / 10);
}
putchar(x % 10 + '0');
}
template<typename T>
inline void write_endl(T x) {
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x) {
write(x);
putchar(' ');
}
}
using namespace IO;
const int N = 2e6 + 10, mod = 1e9 + 7;
int n, pos[N], fa[N], vis[N], nxt[N], t, col[N], ans = 1;
int getfa(int x) {
if (x != fa[x]) {
fa[x] = getfa(fa[x]);
}
return fa[x];
}
vector<int>e[N];
void dfs(int u, int color) {
col[u] = color;
for (auto v : e[u]) {
if (!col[v]) {
dfs(v, 3 - color);
} else if (col[v] != 3 - color) {
ans = 0;
return;
}
}
}
signed main() {
#ifdef luoshen
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
read(n);
for (int i = 1; i <= n; i++) {
int l, r;
read(l), read(r);
pos[l] = pos[r] = i;
}
for (int i = 1; i <= n + 1; i++) {
nxt[i] = fa[i] = i;
vis[i] = 0;
}
for (int i = 1; i <= n * 2; i++) {
if (!vis[pos[i]]) {
vis[pos[i]] = ++t;
} else {
int p = vis[pos[i]];
fa[p] = getfa(p + 1);
int now = fa[p];
while (now <= t) {
e[now].pb(p);
e[p].pb(now);
int Nxt = getfa(nxt[now] + 1);
nxt[now] = t;
now = Nxt;
}
}
}
for (int i = 1; i <= n; i++) {
if (!col[i]) {
dfs(i, 1);
ans = ans * 2 % mod;
}
}
write_endl(ans);
// cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
某位歌姬的故事
题面
加强版[ABC262Ex]
因为本题中范围和权值较大，所以进行一下离散化，将权值全部减一，就变成了加强版的样子了。下面所有分析均基于加强版的数据范围。
将所有限制按限制的权值大小排序，我们可以得到每个下标的权值上限。因为每个限制是限制的最大值，对于一个限制，我们只关心是否有数顶到了上限，我们令顶到了上限的位置为 \(1\)，没顶到上限的为 \(0\)。
不妨设 \(f_{i,j}\) 表示当前位置为 \(i\)，上一个 \(1\) 的位置为 \(j\) 的方案数，转移有三种。
- 在当前位置放个 \(0\)，\(f_{i-1,j}\times x_i\rightarrow f_{i,j}\)。其中 \(x_i\) 表示位置 \(i\) 的上限。
- 在当前位置放个 \(1\)，\(f_{i-1,j}\rightarrow f_{i,i}\)。
- 限制区间 \([l,i]\) 内必须有一个 \(1\)，\(f_{i,[0,l-1]}=0\)。
可以用自己喜欢的方式维护。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10,mod=998244353;
int rid[N],idx,n,m,k,ans=1;
int val[N],f[N],len[N];
map<int,int>id;
vector<int>v[N],g[N],pos[N],Pos;
int get(int x){
if(id.count(x)){
return id[x];
}
rid[++idx]=x;
id[x]=idx;
return id[x];
}
struct node{
int l,r,val;
}seg[N];
bool cmp(node x,node y){
return x.val<y.val;
}
int qpow(int a,int b){
int res=1;
while(b){
if(b&1){
res=res*a%mod;
}
a=a*a%mod;
b>>=1;
}
return res;
}
int query(int x){
if(rid[x]==0){
return 1;
}
int sum=1,mul=1,it=0,siz=v[x].size();
for(int i=0;i<=siz;i++){
vector<int>().swap(pos[i]);
}
for(int i=1;i<=siz;i++){
len[i]=Pos[v[x][i-1]]-Pos[v[x][i-1]-1];
}
for(auto p:g[x]){
int l=lower_bound(v[x].begin(),v[x].end(),seg[p].l)-v[x].begin()+1;
int r=upper_bound(v[x].begin(),v[x].end(),seg[p].r)-v[x].begin();
if(l>r){
return 0;
}
pos[r].pb(l);
}
for(int i=0;i<=siz;i++){
f[i]=0;
}
f[0]=1;
x=rid[x];
for(int i=1;i<=siz;i++){
int mx=-1;
for(auto p:pos[i]){
mx=max(mx,p);
}
int a=qpow(x,len[i]),b=(qpow(x+1,len[i])-a+mod)%mod;
mul=mul*a%mod;
f[i]=sum*qpow(mul,mod-2)%mod*b%mod;
sum=(sum*a%mod+f[i]*mul%mod)%mod;
while(it<mx){
sum=(sum-f[it]*mul%mod+mod)%mod;
it++;
}
}
return sum;
}
void clear(){
map<int,int>().swap(id);
for(int i=0;i<=idx;i++){
vector<int>().swap(v[i]);
vector<int>().swap(g[i]);
rid[i]=0;
}
idx=0;
ans=1;
vector<int>().swap(Pos);
}
void solve(){
read(n),read(k),read(m);
m--;
get(m+1);
Pos.pb(1),Pos.pb(n+1);
ans=1;
for(int i=1;i<=k;i++){
read(seg[i].l),read(seg[i].r),read(seg[i].val);
seg[i].val--;
Pos.pb(seg[i].l),Pos.pb(seg[i].r+1);
}
sort(Pos.begin(),Pos.end());
Pos.erase(unique(Pos.begin(),Pos.end()),Pos.end());
n=Pos.size()-1;
for(int i=1;i<=k;i++){
seg[i].l=lower_bound(Pos.begin(),Pos.end(),seg[i].l)-Pos.begin()+1;
seg[i].r=lower_bound(Pos.begin(),Pos.end(),seg[i].r+1)-Pos.begin();
}
set<int>s;
for(int i=1;i<=n;i++){
s.insert(i);
val[i]=m+1;
}
sort(seg+1,seg+k+1,cmp);
for(int i=1;i<=k;i++){
g[get(seg[i].val)].pb(i);
}
for(int i=1;i<=k;i++){
for(auto it=s.lower_bound(seg[i].l);it!=s.end()&&(*it)<=seg[i].r;it=s.erase(it)){
val[*it]=seg[i].val;
}
}
for(int i=1;i<=n;i++){
v[get(val[i])].pb(i);
}
for(auto x:v[1]){
ans=ans*qpow(m+1,Pos[x]-Pos[x-1])%mod;
}
for(int i=2;i<=idx;i++){
ans=ans*query(i)%mod;
}
write_endl(ans);
clear();
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}