题解：P14271 ABC428F 加强版
由于赛时没做出弱化版，于是恶补分块后来挑战这道题。
我们观察到弱化版，有一个性质，就是说后面的区间一定会包含前面的区间，所以
但是这道题不满足这个性质，于是好像只剩下分块能用了。
考虑每
我们先考虑查询怎么做。
对于散块你可以直接暴力带上 tag 统计是否包含。
对于整块按如下方法整理。
-
如果所有区间向左端对齐，也就是打了
1 操作的tag，那么可以将区间按长度从小到大排序，然后就可以转化成弱化版的3 操作去二分了，所以需要维护一个块内所有区间长度排序后的数组。 -
如果所有区间向右端对齐，那么也可以转化成弱化版的
3 操作，但是由于输入的区间是左闭右开的，所以要仔细处理细节。 -
如果区间没有
tag，那么考虑一个块的答案等于所有小于等于x 的l 的个数减去所有小于等于x 的r 的个数，于是还要维护所有l 和所有r 排序后的数组。
所以时间复杂度为
现在考虑如何修改。
对于整块可以直接覆盖原来标记，这是容易的。
对于散块可以先把散块的标记暴力下传，然后处理修改后再暴力维护
时间复杂度
我不太会算
由于数据或常数原因，我
::::success[Code]
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10,B=91;
int n,m,pl[N],pr[N],ct;
int ql[N],qr[N],id[N];
int tp[N],pos[N],len[N],fl[N],fr[N];
void turn(int x,int tp,int pos){
int ln=pr[x]-pl[x];
if(tp==-1){
pl[x]=pos,pr[x]=pos+ln;
}else{
pl[x]=pos-ln,pr[x]=pos;
}
}
void pushdown(int x){
if(!tp[x]) return ;
for(int i=ql[x];i<=qr[x];i++) turn(i,tp[x],pos[x]);
tp[x]=pos[x]=0;
}
void cg(int x){
for(int i=ql[x];i<=qr[x];i++) fl[i]=pl[i],fr[i]=pr[i];
sort(fl+ql[x],fl+qr[x]+1);
sort(fr+ql[x],fr+qr[x]+1);
}
void add(int l,int r,int top,int ps){
if(id[l]==id[r]){
pushdown(id[l]);
for(int i=l;i<=r;i++) turn(i,top,ps);
cg(id[l]);
return;
}
for(int i=id[l]+1;i<id[r];i++) tp[i]=top,pos[i]=ps;
if(l==ql[id[l]]) tp[id[l]]=top,pos[id[l]]=ps;
else{
pushdown(id[l]);
for(int i=l;i<=qr[id[l]];i++) turn(i,top,ps);
cg(id[l]);
}
if(r==qr[id[r]]) tp[id[r]]=top,pos[id[r]]=ps;
else{
pushdown(id[r]);
for(int i=ql[id[r]];i<=r;i++) turn(i,top,ps);
cg(id[r]);
}
}
int find1(int x,int k){
if(tp[x]==-1){
if(k<pos[x]) return 0;
k=k-pos[x]+1;
int p=upper_bound(len+ql[x],len+qr[x]+1,k)-len;
return qr[x]-p+1;
}else{
if(k>=pos[x]) return 0;
k=pos[x]-k+1;
int p=lower_bound(len+ql[x],len+qr[x]+1,k)-len;
return qr[x]-p+1;
}
}
int find2(int x,int k){
int p=upper_bound(fl+ql[x],fl+qr[x]+1,k)-fl-ql[x];
int q=upper_bound(fr+ql[x],fr+qr[x]+1,k)-fr-ql[x];
return p-q;
}
int ask(int l,int r,int x){
if(id[l]==id[r]){
int ans=0;
for(int i=l;i<=r;i++){
if(!tp[id[l]]) ans+=(pl[i]<=x&&x<pr[i]);
if(tp[id[l]]==-1) ans+=(pos[id[l]]<=x&&x<pos[id[l]]+pr[i]-pl[i]);
if(tp[id[l]]==1) ans+=(pos[id[l]]-pr[i]+pl[i]<=x&&x<pos[id[l]]);
}
return ans;
}
int ans=0;
for(int i=id[l]+1;i<id[r];i++){
if(tp[i]) ans+=find1(i,x);
else ans+=find2(i,x);
}
if(l==ql[id[l]]){
if(tp[id[l]]) ans+=find1(id[l],x);
else ans+=find2(id[l],x);
}
else{
for(int i=l;i<=qr[id[l]];i++){
if(!tp[id[l]]) ans+=(pl[i]<=x&&x<pr[i]);
if(tp[id[l]]==-1) ans+=(pos[id[l]]<=x&&x<pos[id[l]]+pr[i]-pl[i]);
if(tp[id[l]]==1) ans+=(pos[id[l]]-pr[i]+pl[i]<=x&&x<pos[id[l]]);
}
}
if(r==qr[id[r]]){
if(tp[id[r]]) ans+=find1(id[r],x);
else ans+=find2(id[r],x);
}
else{
for(int i=ql[id[r]];i<=r;i++){
if(!tp[id[r]]) ans+=(pl[i]<=x&&x<pr[i]);
if(tp[id[r]]==-1) ans+=(pos[id[r]]<=x&&x<pos[id[r]]+pr[i]-pl[i]);
if(tp[id[r]]==1) ans+=(pos[id[r]]-pr[i]+pl[i]<=x&&x<pos[id[r]]);
}
}
return ans;
}
int qry(int top,int x){
if(!tp[id[x]]){
if(top==-1) return pl[x];
else return pr[x];
}
if(tp[id[x]]==-1){
if(top==-1) return pos[id[x]];
else return pos[id[x]]+pr[x]-pl[x];
}else{
if(top==-1) return pos[id[x]]-pr[x]+pl[x];
else return pos[id[x]];
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>pl[i]>>pr[i];
id[i]=(i-1)/B+1;
len[i]=pr[i]-pl[i]+1;
}
ct=id[n];
for(int i=1;i<=n;i++){
if(!ql[id[i]]) ql[id[i]]=i;
qr[id[i]]=i;
}
for(int i=1;i<=ct;i++){
cg(i);
sort(len+ql[i],len+qr[i]+1);
}
while(m--){
int opt,l,r,c;
cin>>opt>>l>>r>>c;
if(opt==1) add(l,r,-1,qry(-1,c));
if(opt==2) add(l,r,1,qry(1,c));
if(opt==3) cout<<ask(l,r,c)<<"\n";
}
return 0;
}::::
::::info[AI 使用说明]{open}
本题解使用 gpt-5 求出了
::::