LOJ 6277~6285
6277

T1 Block1

区间加,单点查

#include<bits/stdc++.h>
using namespace std;
#define in Read()
int in{
	int i=0,f=1;char ch=0;
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') ch=getchar(),f=-1;
	while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
	return i*f;
}

const int N=5e4+5;
int n,a[N],sz,bl[N],st[N],ed[N],block,add[N];

void modify(int l,int r,int c){
	int p=bl[l],q=bl[r];
	if(p==q){
		for(int i=l;i<=r;++i) a[i]+=c;
		return;
	}else{
		for(int i=p+1;i<=q-1;++i) add[i]+=c;
		for(int i=l;i<=ed[p];++i) a[i]+=c;
		for(int i=st[q];i<=r;++i) a[i]+=c;
		return;
	}
}

int main(){
	n=in;
	for(int i=1;i<=n;++i) a[i]=in;
	sz=sqrt(n);
	block=n/sz;
	if(n%sz) ++block;
	for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1;
	for(int i=1;i<=block;++i) st[i]=(i-1)*sz+1,ed[i]=i*sz;
	ed[block]=min(ed[block],n);
	for(int i=1;i<=n;++i){
		int opt=in,l=in,r=in,c=in;
		if(!opt) modify(l,r,c);
		else printf("%d\n",a[r]+add[bl[r]]);
	}
	return 0;
}

T2 Block2

分块不一定分 n \sqrt n n ,可以通过计算得到更优的块
如利用均值不等式证明等

区间加,查询小于某个值的元素个数
为了降低查询复杂度,要求块内元素有序,二分
注意不能对原序列排序
计算ed时保证ed<n

整块元素不用重排
零散元素加了重排
O ( n n log ⁡ n ) O(n\sqrt n\log\sqrt n) O(nn logn )

#include<bits/stdc++.h>
using namespace std;
#define in Read()
int in{
	int i=0,f=1;char ch=0;
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') ch=getchar(),f=-1;
	while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
	return i*f;
}

#define pb push_back
#define st(x) ((x-1)*sz+1)
#define ed(x) (x*sz)
const int N=1e5+5;
int n,sz,blk,add[N],bl[N],a[N];
vector<int>s[N];

void reset(int x){
	s[x].clear();
	for(int i=st(x);i<=min(ed(x),n);++i) s[x].pb(a[i]);
	sort(s[x].begin(),s[x].end());
}

void modify(int l,int r,int c){
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i) a[i]+=c;
		reset(bl[l]);
		return;
	}else{
		for(int i=l;i<=ed(bl[l]);++i) a[i]+=c;
		reset(bl[l]);
		for(int i=bl[l]+1;i<=bl[r]-1;++i) add[i]+=c;
		for(int i=st(bl[r]);i<=r;++i) a[i]+=c;
		reset(bl[r]);
		return;
	}
}

int query(int l,int r,int c){
	int ans=0;
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i) if(a[i]+add[bl[l]]<c) ++ans;
		return ans;
	}else{
		for(int i=l;i<=ed(bl[l]);++i) if(a[i]+add[bl[l]]<c) ++ans;
		for(int i=bl[l]+1;i<=bl[r]-1;++i)
			ans+=lower_bound(s[i].begin(),s[i].end(),c-add[i])-s[i].begin();
		for(int i=st(bl[r]);i<=r;++i) if(a[i]+add[bl[r]]<c) ++ans;
		return ans;
	}
}

int main(){
	n=in,sz=sqrt(n),blk=n/sz;
	if(n%sz) ++blk;
	for(int i=1;i<=n;++i) a[i]=in;
	for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1,s[bl[i]].pb(a[i]);
	for(int i=1;i<=blk;++i) sort(s[i].begin(),s[i].end());
	for(int i=1;i<=n;++i){
		int op=in,l=in,r=in,c=in;
		if(!op) modify(l,r,c);
		else printf("%d\n",query(l,r,c*c));
	}
	return 0;
}

T3 Block3

区间加,查询某个值的前驱(小于它的最大值)
max,还是要lower_bound

48行符号搞清楚了:>=

#include<bits/stdc++.h>
using namespace std;
#define in Read()
int in{
	int i=0,f=1;char ch=0;
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') ch=getchar(),f=-1;
	while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
	return i*f;
}

#define pb push_back
#define st(x) ((x-1)*sz+1)
#define ed(x) (x*sz)
const int N=1e5+5;
int n,sz,blk,bl[N],a[N],add[N];
vector<int>s[N];

void reset(int x){
	s[x].clear();
	for(int i=st(x);i<=min(ed(x),n);++i) s[x].pb(a[i]);
	sort(s[x].begin(),s[x].end());
}

void modify(int l,int r,int c){
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i) a[i]+=c;
		reset(bl[l]);
		return;
	}else{
		for(int i=l;bl[i]==bl[l];++i) a[i]+=c;
		reset(bl[l]);
		for(int i=bl[l]+1;i<=bl[r]-1;++i) add[i]+=c;
		for(int i=r;bl[i]==bl[r];--i) a[i]+=c;
		reset(bl[r]);
		return;
	}
}

int query(int l,int r,int c){
	int ans=-1;
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i) if(a[i]+add[bl[l]]<c) ans=max(ans,a[i]+add[bl[l]]);
		return ans;
	}else{
		for(int i=l;bl[i]==bl[l];++i) if(a[i]+add[bl[l]]<c) ans=max(ans,a[i]+add[bl[l]]);
		for(int i=bl[l]+1;i<=bl[r]-1;++i){
			if(s[i].front()>=c-add[i]) continue;
			if(s[i].back()<c-add[i]){
				ans=max(ans,s[i].back()+add[i]);
				continue;
			}
			int w=lower_bound(s[i].begin(),s[i].end(),c-add[i])-s[i].begin()-1;
			ans=max(ans,s[i][w]+add[i]);
		}
		for(int i=r;bl[i]==bl[r];--i) if(a[i]+add[bl[r]]<c) ans=max(ans,a[i]+add[bl[r]]);
		return ans;
	}
}

int main(){
	n=in,sz=sqrt(n),blk=n/sz;
	if(n%sz) ++blk;
	for(int i=1;i<=n;++i) a[i]=in;
	for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1,s[bl[i]].pb(a[i]);
	for(int i=1;i<=blk;++i) sort(s[i].begin(),s[i].end());
	for(int i=1;i<=n;++i){
		int op=in,l=in,r=in,c=in;
		if(!op) modify(l,r,c);
		else printf("%d\n",query(l,r,c));
	}
}

T4 Block4

区间加,区间和
一定要开long long
打码5分钟,debug2小时

#include<bits/stdc++.h>
using namespace std;
#define in Read()
#define int long long
int in{
	int i=0,f=1;char ch=0;
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') ch=getchar(),f=-1;
	while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
	return i*f;
}

const int N=1e6+5;
int n,sz,a[N],add[N],blk,bl[N],sum[N];

void modify(int l,int r,int c){
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i) a[i]+=c,sum[bl[i]]+=c;
		return;
	}else{
		for(int i=l;bl[i]==bl[l];++i) a[i]+=c,sum[bl[i]]+=c;
		for(int i=bl[l]+1;i<=bl[r]-1;++i) add[i]+=c,sum[i]+=c*sz;
		for(int i=r;bl[i]==bl[r];--i) a[i]+=c,sum[bl[i]]+=c;
	}
}

int query(int l,int r,int mod){
	int ans=0;
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i)
			(ans+=a[i]+add[bl[i]])%=mod;
		return ans;
	}else{
		for(int i=l;bl[i]==bl[l];++i) (ans+=a[i]+add[bl[i]])%=mod;
		for(int i=bl[l]+1;i<=bl[r]-1;++i) (ans+=sum[i])%=mod;
		for(int i=r;bl[i]==bl[r];--i) (ans+=a[i]+add[bl[i]])%=mod;
		return ans%mod;
	}
}

signed main(){
	n=in,sz=sqrt(n),blk=n/sz;
	if(n%sz) ++blk;
	for(int i=1;i<=n;++i) a[i]=in;
	for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1,sum[bl[i]]+=a[i];
	for(int i=1;i<=n;++i){
		int op=in,l=in,r=in,c=in;
		if(!op) modify(l,r,c);
		else printf("%lld\n",query(l,r,c+1));
	}
	return 0;
}

T5 Block5

区间开方,区间求和

发现0/1开方不变,其余数最多开31次方就会变成0/1
维护全0/1区间即可

#include<bits/stdc++.h>
using namespace std;
#define in Read()
#define int long long
int in{
	int i=0,f=1;char ch=0;
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') ch=getchar(),f=-1;
	while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
	return i*f;
}

const int N=5e4+5;
int n,sz,blk,a[N],sum[N],bl[N];
bool tag[N];

int Sqrt(int x){
	return x?sqrt(x):0;
}

void change(int x){
	if(tag[x]) return;
	int l=(x-1)*sz+1,r=min(x*sz,n);
	bool flag=false;
	for(int i=l;i<=r;++i){
		sum[x]-=a[i];
		a[i]=Sqrt(a[i]);
		sum[x]+=a[i];
		if(a[i]!=0&&a[i]!=1) flag=true;
	}
	tag[x]=flag^1;
}

void modify(int l,int r){
	if(bl[l]==bl[r]){
		if(tag[bl[l]]) return;
		for(int i=l;i<=r;++i){
			sum[bl[i]]-=a[i];
			a[i]=Sqrt(a[i]);
			sum[bl[i]]+=a[i];
		}
		return;
	}
	if(!tag[bl[l]])
		for(int i=l;bl[i]==bl[l];++i){
			sum[bl[i]]-=a[i];
			a[i]=Sqrt(a[i]);
			sum[bl[i]]+=a[i];
		}
	for(int i=bl[l]+1;i<=bl[r]-1;++i) change(i);
	if(!tag[bl[r]])
		for(int i=r;bl[i]==bl[r];--i){
			sum[bl[i]]-=a[i];
			a[i]=Sqrt(a[i]);
			sum[bl[i]]+=a[i];
		}
	return;
}

int query(int l,int r){
	int ans=0;
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i) ans+=a[i];
		return ans;
	}else{
		for(int i=l;bl[i]==bl[l];++i) ans+=a[i];
		for(int i=bl[l]+1;i<=bl[r]-1;++i) ans+=sum[i];
		for(int i=r;bl[i]==bl[r];--i) ans+=a[i];
		return ans;
	}
}

signed main(){
	n=in,sz=Sqrt(n),blk=n/sz;
	if(n%sz) ++blk;
	for(int i=1;i<=n;++i) a[i]=in;
	for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1,sum[bl[i]]+=a[i];
	for(int i=1;i<=n;++i){
		int op=in,l=in,r=in,c=in;
		if(!op) modify(l,r);
		else printf("%lld\n",query(l,r));
	}
	return 0;
}

T6 Block6

单点插单点询问

  1. 分块是暴力算法
  2. 块大小你决定

块太大了重新分块

51行s[id][p-num-1]是因为vector下标[0,size()-1]

#include<bits/stdc++.h>
using namespace std;
#define in Read()
int in{
	int i=0,f=1;char ch=0;
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') ch=getchar(),f=-1;
	while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
	return i*f;
}

#define pb push_back
const int N=1e6+5;
int n,sz,blk,bl[N],a[N];
vector<int>s[N];

void rebuild(){
	int id=0,cnt=0;
	while(!s[id+1].empty()){
		++id;
		for(int i=0;i<s[id].size();++i) a[++cnt]=s[id][i];
		s[id].clear();
	}
	sz=sqrt(cnt);
	for(int i=1;i<=cnt;++i){
		bl[i]=(i-1)/sz+1;
		s[bl[i]].pb(a[i]);
	}
	return;
}

void insert(int p,int v){
	int id=0,num=0;
	while(num+s[id+1].size()<p){
		++id;
		num+=s[id].size();
	}
	++id;
	s[id].insert(p-num-1+s[id].begin(),v);
	if(s[id].size()>=20*sz) rebuild();
	return;
}

int query(int p){
	int id=0,num=0;
	while(num+s[id+1].size()<p){
		++id;
		num+=s[id].size();
	}
	++id;
	return s[id][p-num-1];
}

int main(){
	n=in,sz=sqrt(n);
	for(int i=1;i<=n;++i) a[i]=in;
	for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1,s[bl[i]].pb(a[i]);
	for(int i=1;i<=n;++i){
		int op=in,l=in,r=in,c=in;
		if(!op) insert(l,r);
		else printf("%d\n",query(r));
	}
	return 0;
}

T7 Block7

单点乘,单点加,单点查
线段树2
乘法优先

#include<bits/stdc++.h>
using namespace std;
#define in Read()
int in{
	int i=0,f=1;char ch=0;
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') ch=getchar(),f=-1;
	while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
	return i*f;
}

#define debug puts("qwq")

const int N=1e5+5,mod=1e4+7;
int n,sz,bl[N],a[N],plu[N],tim[N],blk;

int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
int mul(int a,int b){return 1ll*a*b%mod;}

void push_down(int b){
	
	for(int i=(b-1)*sz+1;bl[i]==b;++i)
		a[i]=add(mul(a[i],tim[b]),plu[b]);
		
	tim[b]=1;plu[b]=0;
	return;
	
}

void modify_add(int l,int r,int c){
	if(bl[l]==bl[r]){
		
		push_down(bl[l]);
		for(int i=l;i<=r;++i)
			a[i]=add(a[i],c);
		return;
		
	}else{
		
		push_down(bl[l]);
		push_down(bl[r]);
		
		for(int i=l;bl[i]==bl[l];++i)
			a[i]=add(a[i],c);
		for(int i=bl[l]+1;i<=bl[r]-1;++i)
			plu[i]=add(plu[i],c);
		for(int i=r;bl[i]==bl[r];--i)
			a[i]=add(a[i],c);
			
		return;
	}
}

void modify_mul(int l,int r,int c){
	if(bl[l]==bl[r]){
		
		push_down(bl[l]);
		for(int i=l;i<=r;++i)
			a[i]=mul(a[i],c);
		return;
		
	}else{
		
		push_down(bl[l]);
		push_down(bl[r]);
		
		for(int i=l;bl[i]==bl[l];++i)
			a[i]=mul(a[i],c);
		for(int i=bl[l]+1;i<=bl[r]-1;++i)
			tim[i]=mul(tim[i],c),
			plu[i]=mul(plu[i],c);
		for(int i=r;bl[i]==bl[r];--i)
			a[i]=mul(a[i],c);
		return;
		
	}
}

int query(int p){
	
	push_down(bl[p]);
	return a[p];
	
}

int main(){
	n=in,sz=sqrt(n),blk=n/sz;
	if(n%sz) ++blk;
	
	for(int i=1;i<=n;++i) a[i]=in;
	for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1;
	for(int i=1;i<=blk;++i) tim[i]=1;
	
	for(int i=1;i<=n;++i){
		int op=in,l=in,r=in,c=in;
		if(op==0) modify_add(l,r,c);
		else if(op==1) modify_mul(l,r,c);
		else printf("%d\n",query(r)); 
	}
	
	return 0;
}

T8 Block8

区间改区间查

#include<bits/stdc++.h>
using namespace std;
#define in Read()
int in{
	int i=0,f=1;char ch=0;
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') ch=getchar(),f=-1;
	while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
	return i*f;
}

const int N=1e5+5;
int n,sz,blk,a[N],tag[N],bl[N];

void push_down(int b){
	if(tag[b]==-1) return;
	for(int i=(b-1)*sz+1;bl[i]==b;++i)
		a[i]=tag[b];
	tag[b]=-1;
}

int query(int l,int r,int c){
	int ans=0;
	if(bl[l]==bl[r]){
		push_down(bl[l]);
		for(int i=l;i<=r;++i){
			if(a[i]==c) ++ans;
			a[i]=c;
		}
		return ans;
	}else{
		push_down(bl[l]);
		push_down(bl[r]);
		
		for(int i=l;bl[i]==bl[l];++i)
			if(a[i]==c) ++ans;
			else a[i]=c;
		for(int i=r;bl[i]==bl[r];--i)
			if(a[i]==c) ++ans;
			else a[i]=c;
		for(int i=bl[l]+1;i<=bl[r]-1;++i){
			if(tag[i]==-1){
				for(int j=(i-1)*sz+1;bl[j]==i;++j)
					if(a[j]==c) ++ans;
					else a[j]=c;
				tag[i]=c;
			}else{
				if(tag[i]==c) ans+=sz;
				else tag[i]=c;
			}
		}
		
		return ans;
	}
}

int main(){
	n=in,sz=sqrt(n);
	for(int i=1;i<=n;++i) a[i]=in;
	for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1;
	for(int i=1;i<=n;i+=sz) tag[bl[i]]=-1;
	for(int i=1;i<=n;++i){
		int l=in,r=in,c=in;
		printf("%d\n",query(l,r,c));
	}
	return 0;
}

T9 Block9

蒲公英
求最小众数

蒲公英掉紫了😭
黑色经验-1

n ≤ 4 e 4 , a i ≤ 1 e 9 n\le 4e4,a_i\le 1e9 n4e4,ai1e9,离散化
竟然不带修,多美好的世界

预处理
s i , j s_{i,j} si,j表示第 i i i块中 j j j的出现次数
p i , j p_{i,j} pi,j表示第 i i i块到第 j j j块的众数

那么 [ l , r ] [l,r] [l,r]的众数为整块众数和散装中数的并集,统计这些数个数即可

用桶统计, p o t [ i ] ≤ 2 n + 1 pot[i]\le 2\sqrt n+1 pot[i]2n +1
整块类前缀和, O ( 1 ) O(1) O(1);总查询 O ( n ) O(\sqrt n) O(n )

预处理:
s i , j s_{i,j} si,j前缀和
p i , j p_{i,j} pi,j,枚举 i , j i,j i,j,利用 s i , j s_{i,j} si,j更新

#include<bits/stdc++.h>
using namespace std;
#define in Read()
int in{
	int i=0,f=1;char ch=0;
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') ch=getchar(),f=-1;
	while(isdigit(ch)) i=(i<<3)+(i<<1)+ch-48,ch=getchar();
	return i*f;
}

#define pb push_back
const int N=1e5+5,M=1e3+5,inf=2147483647;
int n,sz,lim;
int bl[N],a[N],val[N];
int s[M][N],p[M][M];
int pot[N];
vector<int>inpot;

void discretize(){
	sort(a+1,a+n+1);
	int len=unique(a+1,a+n+1)-a-1;
	for(int i=1;i<=n;++i){
		val[i]=lower_bound(a+1,a+n+1,val[i])-a;
		lim=max(lim,val[i]);
	}
	return;
}

void prepare(){
	for(int i=1;i<=n;++i)
		++s[bl[i]][val[i]];
	for(int i=1;i<=bl[n];++i)
		for(int j=1;j<=lim;++j)
			s[i][j]+=s[i-1][j];
	for(int i=1;i<=bl[n];++i)
		for(int j=i;j<=bl[n];++j){
			int mode=inf,cnt=0;
			for(int k=(j-1)*sz+1;bl[k]==j;++k){
				if(cnt<s[j][val[k]]-s[i-1][val[k]]){
					cnt=s[j][val[k]]-s[i-1][val[k]];
					mode=val[k];
				}
				if(cnt==s[j][val[k]]-s[i-1][val[k]]&&mode>val[k])	
					mode=val[k];
			}
			if(i!=j){
				int k=p[i][j-1];
				if(cnt<s[j][k]-s[i-1][k]){
					mode=k;
					cnt=s[j][k]-s[i-1][k];
				}
				if(cnt==s[j][k]-s[i-1][k]&&mode>k)
					mode=k;
			}
			p[i][j]=mode;
		}
	return;
}

int query(int l,int r){
	if(!inpot.empty()){
		for(int i=0;i<inpot.size();++i)
			pot[inpot[i]]=0;
		inpot.clear();
	}
	int mode=inf,cnt=0;
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i){
			++pot[val[i]];
			if(pot[val[i]]>cnt){
				cnt=pot[val[i]];
				mode=val[i];
			}
			if(pot[val[i]]==cnt&&mode>val[i])
				mode=val[i];
			inpot.pb(val[i]);
		}
		return mode;
	}else{
		for(int i=l;bl[i]==bl[l];++i){
			if(!pot[val[i]])
				pot[val[i]]+=s[bl[r]-1][val[i]]-s[bl[l]][val[i]];
			pot[val[i]]++;
			if(pot[val[i]]>cnt){
				cnt=pot[val[i]];
				mode=val[i];
			}
			if(pot[val[i]]==cnt&&mode>val[i])
				mode=val[i];
			inpot.pb(val[i]);
		}
		for(int i=r;bl[i]==bl[r];--i){
			if(!pot[val[i]])
				pot[val[i]]+=s[bl[r]-1][val[i]]-s[bl[l]][val[i]];
			pot[val[i]]++;
			if(pot[val[i]]>cnt){
				cnt=pot[val[i]];
				mode=val[i];
			}
			if(pot[val[i]]==cnt&&mode>val[i])
				mode=val[i];
			inpot.pb(val[i]);
		}
		if(bl[r]==bl[l]+1) return mode;
		int mone=p[bl[l]+1][bl[r]-1];
		if(pot[mone]) return mode;
		pot[mone]+=s[bl[r]-1][mone]-s[bl[l]][mone];
		if(pot[mone]>cnt){
			mode=mone;
			cnt=pot[mone];
		}
		if(pot[mone]==cnt&&mone<mode)
			mode=mone;
		inpot.pb(mone);
		return mode;
	}
}

int main(){
	n=in,sz=sqrt(n);
	for(int i=1;i<=n;++i) val[i]=a[i]=in;
	for(int i=1;i<=n;++i) bl[i]=(i-1)/sz+1;
	discretize();
	prepare();
	for(int i=1;i<=n;++i){
		int l=in,r=in;
		printf("%d\n",a[query(l,r)]);
	}
	return 0;
}

其余练习

上帝造题的七分钟2 / 花神游历各国
蒲公英

Logo

瓜分20万奖金 获得内推名额 丰厚实物奖励 易参与易上手

更多推荐