题目链接
题目解法
这么牛的题！！！
我第一眼看到 偶\(-\)奇 想到的是 LGV /xk
有一堆线段的题先考虑有没有线段之间的特殊关系
这道题中，如果有线段 \(x\) 包含线段 \(y\)，则线段 \(x\) 是无用的，因为如果选了 \(x\)，那么选不选 \(y\) 无所谓，因为是 偶\(-\)奇，所以贡献抵消了
现在的线段已经是互补包含的了
考虑拎出所有属于 \([l,r]\) 之间的线段（令左端点为 \(l\) 的线段为 \(st\)，右端点为 \(r\) 的线段为 \(ed\)）
若有 \(l_{st}<l_{st+1}<l_{st+2}<r_{st}\)，则线段 \(st+2\) 是无用的，为什么？
- 角度1
如果同时选线段 \(st,st+2\)，则线段 \(st+1\) 可选可不选，贡献抵消了 - 角度2
用朴素的 \(dp\) 解释，令 \(f_i\) 为以线段 \(i\) 为结尾的贡献
转移式为 \(f_i=\sum\limits_{j<i,l_i\le r_j}f_j\)
显然 \(f_{st}=1,f_{st+1}=-1,f_{st+2}=0\)
把无用的线段去掉之后，我们选择的方案是唯一的，这个往后手推一下角度 2 中的 \(f\) 可以得出
上面的做法看起来不太能上 \(ds\) 优化
考虑换个角度看这个做法
假设当前的线段为 \(x\)，则下次的下次的线段是满足 \(l_y>r_x\) 的最小的 \(y\)
我们从 \(st\) 和 \(st+1\) 分别往后跳，能跳到 \(ed\) 答案就 \(\neq 0\)，至于到底是 \(-1\) 还是 \(1\) 就看路径长度的奇偶性
往后跳的过程可以用倍增优化
时间复杂度 \(O((n+m)\log n)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
FF=0;int RR=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
FF*=RR;
}
const int N=400010;
int n,m,up[N][20];
int disc[N],cnt;
#define lowbit(x) x&-x
struct fenwick{
int tr[N];
void add(int x){ for(;x<=cnt;x+=lowbit(x)) tr[x]++;}
int ask(int x){ int res=0;for(;x;x-=lowbit(x)) res+=tr[x];return res;}
}tr;
#define l first
#define r second
pii org[N],seg[N],rvs[N];
vector<int> range[N];
int jump(int x,int ed){ DF(i,18,0) if(up[x][i]<=ed) x=up[x][i];return x;}
int main(){
read(n),read(m);
F(i,1,n){
read(org[i].l),read(org[i].r);
disc[++cnt]=org[i].l,disc[++cnt]=org[i].r;
}
sort(disc+1,disc+cnt+1);
cnt=unique(disc+1,disc+cnt+1)-disc-1;
F(i,1,n){
org[i].l=lower_bound(disc+1,disc+cnt+1,org[i].l)-disc;
org[i].r=lower_bound(disc+1,disc+cnt+1,org[i].r)-disc;
range[org[i].l].pb(org[i].r);
}
int len=0;
DF(l,cnt,1){
sort(range[l].begin(),range[l].end());
for(int r:range[l]){
if(!tr.ask(r)) seg[++len]={disc[l],disc[r]},rvs[len]={disc[r],disc[l]};
tr.add(r);
}
}
reverse(seg+1,seg+len+1),reverse(rvs+1,rvs+len+1);
int j=len+1;
DF(i,len,1){
while(seg[j-1].l>seg[i].r) j--;
up[i][0]=j;
}
F(j,0,18) up[len+1][j]=len+1;
F(j,1,18) F(i,1,len) up[i][j]=up[up[i][j-1]][j-1];
while(m--){
int lo,hi;read(lo),read(hi);
int st=lower_bound(seg+1,seg+len+1,pair{lo,-1})-seg;
int ed=lower_bound(rvs+1,rvs+len+1,pair{hi,-1})-rvs;
if(seg[st].l!=lo||seg[ed].r!=hi){ puts("0");continue;}
int cur1=jump(st,ed),cur2=jump(st+1,ed);
if(cur1==cur2) puts("0");
else if(cur1==ed) puts("998244352");
else if(cur2==ed) puts("1");
else puts("0");
}
return 0;
}