专栏文章

题解：P6749 『MdOI R3』Yoshino

cccx25350110
P6749题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minxeml9
此快照首次捕获于
2025/12/02 09:55
3 个月前
此快照最后确认于
2025/12/02 09:55
3 个月前
查看原文
珂朵莉树，(l,r,v)(l,r,v) 表示 [l,r][l,r] 是一个 首项为 vv 的等差数列。经典 O(n+q)O(n+q)。
拆贡献，现在赋值区间 [l,r][l,r]，值域是 [v,v+r−l][v,v+r-l] 记为 [L,R][L,R]。
区间 [l,r][l,r] 中没有新的逆序对。
区间 [1,l−1][1,l-1] 值域在 [L,R][L,R] 的数 xx 有 x−Lx-L 个数比她小。区间 [r+1,n][r+1,n] 同理。需要求区间值域在 [L,R][L,R] 之间的数的和和数量。
需要实现行加矩阵求和。
分块套树状数组，整块打标记，散块重构。
懂得都懂，复杂度 O(n(n+q)log⁡n)O(\sqrt n (n+q) \log n)。不懂的看代码。
重工业代码。
CPP
#include<bits/stdc++.h>
#define N 30005
#define gcd __gcd
#define inf LONG_LONG_MAX
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
#define fr first
#define se second
#define rd read()
#define V 30000
#define IT set<node>::iterator 
#define md 998244353
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
const int block=1000,S=N/block+5;
int A[N],n,m,q,l,r,v,op,ans;
inline int read()
{
	int x=0,f=1;
	char ch=gc;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=gc;
	}
	while(ch>='0' && ch<='9')
		x=x*10+ch-'0',ch=gc;
	return x*f;
}
inline int getsum(int l,int r,int L,int R,int v){int s=max(l,L-v+1),t=min(r,R-v+1);if(s>t) return 0;int k=t-s+1;return max(k*(v-1)+(s+t)*k/2,0);}
inline int getcnt(int l,int r,int L,int R,int v){return max(min(r,R-v+1)-max(l,L-v+1)+1,0);}
struct ODT{
	int ans;
	struct blk{
		struct BIT{
			int tr[N];
			inline void add(int x,int v){if(!x) return;for(;x<=V;x+=x&-x) tr[x]+=v;}
			inline int Ask(int x){int res=0;for(;x;x^=x&-x) res+=tr[x];return res;}
			inline int ask(int l,int r){return Ask(r)-Ask(l-1);}
		}T1[S],T2[S];
		int a[N],tot,bl[N],R[N],L[N],tag[N];
		inline void build(){
			for(int i=1;i<=n;i++) a[i]=-1,bl[i]=(i-1)/block+1;
			tot=bl[n];
			for(int i=1;i<=tot;i++){R[i]=i*block;L[i]=R[i-1]+1;}
			R[tot]=n;
		}
		inline void pushdown(int x){if(tag[x]){for(int i=L[x];i<=R[x];i++) a[i]=tag[x]+i-L[x];}tag[x]=0;}
		inline void clear(int x){for(int i=L[x];i<=R[x];i++){if(a[i]!=-1) T1[x].add(a[i],-a[i]),T2[x].add(a[i],-1);}}
		inline void init(int x){for(int i=L[x];i<=R[x];i++){if(a[i]!=-1) T1[x].add(a[i],a[i]),T2[x].add(a[i],1);}}
		inline void modify(int l,int r,int v){
			if(l>r) return;
			if(bl[l]==bl[r]){
				clear(bl[l]);pushdown(bl[l]);
				for(int i=l;i<=r;i++) a[i]=v+i-l;
				init(bl[l]);
				return;
			}
			clear(bl[l]);pushdown(bl[l]);
			for(int i=l;i<=R[bl[l]];i++) a[i]=v+i-l;
			init(bl[l]);v+=R[bl[l]]-l+1;
			for(int i=bl[l]+1;i<bl[r];i++){
				tag[i]=v; 
				v+=R[i]-L[i]+1;
			}
			clear(bl[r]);pushdown(bl[r]);
			for(int i=L[bl[r]];i<=r;i++) a[i]=v+i-L[bl[r]];
			init(bl[r]);
		}
		inline int asksum(int l,int r,int x,int y){
			if(l>r||x>y) return 0;
			int res=0;
			if(bl[l]==bl[r]){
				if(tag[bl[l]]){res=getsum(l-L[bl[l]]+1,r-L[bl[l]]+1,x,y,tag[bl[l]]);}
				else{
					for(int i=l;i<=r;i++){
						if(x<=a[i]&&a[i]<=y) res+=a[i];
					}
				}
				return res;
			}
			if(tag[bl[l]]){res+=getsum(l-L[bl[l]]+1,R[bl[l]]-L[bl[l]]+1,x,y,tag[bl[l]]);}
			else{
				for(int i=l;i<=R[bl[l]];i++){
					if(x<=a[i]&&a[i]<=y) res+=a[i];
				}
			}
			for(int i=bl[l]+1;i<bl[r];i++){
				if(tag[i]) res+=getsum(1,R[i]-L[i]+1,x,y,tag[i]);
				else res+=T1[i].ask(x,y);
			}
			if(tag[bl[r]]){res+=getsum(1,r-L[bl[r]]+1,x,y,tag[bl[r]]);}
			else{
				for(int i=L[bl[r]];i<=r;i++){
					if(x<=a[i]&&a[i]<=y) res+=a[i];
				}
			}
			return res;
		}
		inline int askcnt(int l,int r,int x,int y){
			if(l>r||x>y) return 0;
			int res=0;
			if(bl[l]==bl[r]){
				if(tag[bl[l]]){res=getcnt(l-L[bl[l]]+1,r-L[bl[l]]+1,x,y,tag[bl[l]]);}
				else{
					for(int i=l;i<=r;i++){
						if(x<=a[i]&&a[i]<=y) res++;
					}
				} 
				return res;
			}
			if(tag[bl[l]]){res+=getcnt(l-L[bl[l]]+1,R[bl[l]]-L[bl[l]]+1,x,y,tag[bl[l]]);}
			else{
				for(int i=l;i<=R[bl[l]];i++){
					if(x<=a[i]&&a[i]<=y) res++;
				}
			}
			for(int i=bl[l]+1;i<bl[r];i++){
				if(tag[i]) res+=getcnt(1,R[i]-L[i]+1,x,y,tag[i]);
				else res+=T2[i].ask(x,y);
			}
			if(tag[bl[r]]){res+=getcnt(1,r-L[bl[r]]+1,x,y,tag[bl[r]]);}
			else{
				for(int i=L[bl[r]];i<=r;i++){
					if(x<=a[i]&&a[i]<=y) res++;
				}
			}
			return res;
		}
	}G;	
	struct node{
		int l,r,v;
		node(int L,int R=0,int w=0):l(L),r(R),v(w){};
		inline bool operator <(const node &o)const{return l<o.l;}
	};	
	set<node>s;
	inline IT split(int pos){
		IT it=s.lower_bound(node(pos));
		if(it!=s.end()&&it->l==pos) return it;
		--it;
		int l=it->l,r=it->r,v=it->v;
		s.erase(it);s.insert(node(l,pos-1,v));
		return s.insert(node(pos,r,v==-1?-1:v+pos-l)).first;
	}
	inline void assign(int l,int r,int v){
		IT itr=split(r+1),itl=split(l);
		for(IT it=itl;it!=itr;++it){
			int L=it->l,R=it->r,w=it->v;
			if(w!=-1) ans-=(G.asksum(1,l-1,w,w+R-L)-G.askcnt(1,l-1,w,w+R-L)*w),ans-=(G.askcnt(R+1,n,w,w+R-L)*(w+R-L)-G.asksum(R+1,n,w,w+R-L));
			if(w!=-1) ans-=(G.askcnt(1,l-1,w+R-L+1,V)*(R-L+1)),ans-=(G.askcnt(R+1,n,1,w-1)*(R-L+1));
		}
		s.erase(itl,itr);
		s.insert(node(l,r,v)); 
		ans+=(G.asksum(1,l-1,v,v+r-l)-G.askcnt(1,l-1,v,v+r-l)*v)+(-G.asksum(r+1,n,v,v+r-l)+G.askcnt(r+1,n,v,v+r-l)*(v+r-l));
		ans+=(G.askcnt(1,l-1,v+r-l+1,V)*(r-l+1));ans+=(G.askcnt(r+1,n,1,v-1)*(r-l+1));
		G.modify(l,r,v);
	}
	inline void init(){s.insert(node(1,n,-1));G.build();}
}ct;
signed main(){
	n=rd,m=rd;
	for(int i=1;i<=n;i++) A[i]=rd;
	ct.init();
	for(int i=1;i<=n;i++) ct.assign(i,i,A[i]);
	for(int i=1;i<=m;i++){
		op=rd;
		if(op==2) cout<<ct.ans<<'\n';
		else l=rd,r=rd,v=rd,ct.assign(l,r,v);
	}
	return 0;	 
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...