标签：10 入门分块 LOJ void write int flag getchar

LOJ 数列分块 \(1\sim 9\)

T1

区间加，单点查。

没啥好说的，分块都不想写。树状数组 + 差分解决。

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
//#define int long long
using namespace std;
template<typename T> void read(T &k)
{
	k=0;T flag=1;char b=getchar();
	while (!isdigit(b)) {flag=(b=='-')?-1:1;b=getchar();}
	while (isdigit(b)) {k=k*10+b-48;b=getchar();}
	k*=flag;
}
template<typename T> void write(T k) {if (k<0) {putchar('-'),write(-k);return;}if (k>9) write(k/10);putchar(k%10+48);}
template<typename T> void writewith(T k,char c) {write(k);putchar(c);}
#define lowbit(_) (_&-_)
const int _SIZE=5e4;
int n,sum[_SIZE+5];
void update(int x,int v) {for (;x<=n;x+=lowbit(x)) sum[x]+=v;}
int query(int x)
{
	int res=0;
	for (;x;x-=lowbit(x)) res+=sum[x];
	return res;
}
int a[_SIZE+5],diff[_SIZE+5];
signed main()
{
	read(n);
	for (int i=1,temp;i<=n;i++) read(a[i]),diff[i]=a[i]-a[i-1];
	for (int i=1;i<=n;i++) update(i,diff[i]);
	for (int i=1;i<=n;i++)
	{
		int opt,l,r,c;read(opt),read(l),read(r),read(c);
		if (opt==0) update(l,c),update(r+1,-c);
		else writewith(query(r),'\n');
	}
	return 0;
}

T2

区间加，区间查比 \(k\) 小的数。

先将原数列分块，对每一个块开一个 vector，将数列元素存入 vector，并将 vector 排序，对于询问，在散块暴力统计，整块直接在 vector 中二分即可。

对于修改操作，整块直接打标记即可，散块暴力修改，然后暴力重构散块的 vector 并排序。

总时间复杂度 \(\mathcal O(n\sqrt n\log n)\)。

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
//#define int long long
using namespace std;
template<typename T> void read(T &k)
{
	k=0;T flag=1;char b=getchar();
	while (!isdigit(b)) {flag=(b=='-')?-1:1;b=getchar();}
	while (isdigit(b)) {k=k*10+b-48;b=getchar();}
	k*=flag;
}
template<typename T> void write(T k) {if (k<0) {putchar('-'),write(-k);return;}if (k>9) write(k/10);putchar(k%10+48);}
template<typename T> void writewith(T k,char c) {write(k);putchar(c);}
const int _SIZE=5e4,_BLOCK=1e3;
int pos[_BLOCK+5],bl[_BLOCK+5],br[_BLOCK+5],tag[_BLOCK+5];
int a[_SIZE+5],cnt,len,n;
vector<int> block[_BLOCK+5];
void init()
{
	len=sqrt(n),cnt=(n-1)/len+1;
	for (int i=1;i<=cnt;i++)
		bl[i]=(i-1)*len+1,br[i]=min(n,i*len);
	for (int i=1;i<=cnt;i++)
	{
		for (int j=bl[i];j<=br[i];j++)
		{
			pos[j]=i;
			block[i].push_back(a[j]);
		}
		sort(block[i].begin(),block[i].end());
	}
}
void rebuild(int id)
{
	vector<int>().swap(block[id]);
	for (int i=bl[id];i<=br[id];i++) block[id].push_back(a[i]);
	sort(block[id].begin(),block[id].end());
}
void add(int l,int r,int c)
{
	if (pos[l]==pos[r])
	{
		for (int i=l;i<=r;i++) a[i]+=c;
		rebuild(pos[l]);
	}
	else
	{
		for (int i=l;i<=br[pos[l]];i++) a[i]+=c;
		rebuild(pos[l]);
		for (int i=pos[l]+1;i<pos[r];i++) tag[i]+=c;
		for (int i=bl[pos[r]];i<=r;i++) a[i]+=c;
		rebuild(pos[r]);
	}
}
int query(int l,int r,int c)
{
	int res=0;
	if (pos[l]==pos[r])
	{
		for (int i=l;i<=r;i++) res+=(a[i]+tag[pos[l]])<c;
		return res;
	}
	else
	{
		for (int i=l;i<=br[pos[l]];i++) res+=(a[i]+tag[pos[l]])<c;
		for (int i=pos[l]+1;i<pos[r];i++)
			res+=lower_bound(block[i].begin(),block[i].end(),c-tag[i])-block[i].begin();
		for (int i=bl[pos[r]];i<=r;i++) res+=(a[i]+tag[pos[r]])<c;
		return res;
	}
}
signed main()
{
	read(n);
	for (int i=1;i<=n;i++) read(a[i]);
	init();
	for (int i=1;i<=n;i++)
	{
		int opt,l,r,c;
		read(opt),read(l),read(r),read(c);
		if (opt==0) add(l,r,c);
		else writewith(query(l,r,c*c),'\n');
	}
	return 0;
}

T3

区间加，区间查询前驱。

和 \(2\) 的思路近乎相同，同样是用 vector 维护块内有序数列，然后散块暴力，整块二分即可。注意要判断块内无解的情况。

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
//#define int long long
using namespace std;
template<typename T> void read(T &k)
{
	k=0;T flag=1;char b=getchar();
	while (!isdigit(b)) {flag=(b=='-')?-1:1;b=getchar();}
	while (isdigit(b)) {k=k*10+b-48;b=getchar();}
	k*=flag;
}
template<typename T> void write(T k) {if (k<0) {putchar('-'),write(-k);return;}if (k>9) write(k/10);putchar(k%10+48);}
template<typename T> void writewith(T k,char c) {write(k);putchar(c);}
const int _SIZE=1e5,_BLOCK=1e5;
int pos[_SIZE+5],bl[_BLOCK+5],br[_BLOCK+5],tag[_BLOCK+5];
vector<int> block[_BLOCK+5];
int a[_SIZE+5],n,len,cnt;
void init()
{
	len=sqrt(n),cnt=(n-1)/len+1;
	for (int i=1;i<=cnt;i++)
		bl[i]=(i-1)*len+1,br[i]=min(n,len*i);
	for (int i=1;i<=cnt;i++)
	{
		for (int j=bl[i];j<=br[i];j++)
		{
			pos[j]=i;
			block[i].push_back(a[j]);
		}
		sort(block[i].begin(),block[i].end());
	}
}
void rebuild(int id)
{
	block[id].clear();
	for (int i=bl[id];i<=br[id];i++) block[id].push_back(a[i]);
	sort(block[id].begin(),block[id].end());
}
void add(int l,int r,int c)
{
	
	if (pos[l]==pos[r])
	{
		for (int i=l;i<=r;i++) a[i]+=c;
		rebuild(pos[l]);
	}
	else
	{
		for (int i=l;i<=br[pos[l]];i++) a[i]+=c;
		for (int i=pos[l]+1;i<pos[r];i++) tag[i]+=c;
		for (int i=bl[pos[r]];i<=r;i++) a[i]+=c;
		rebuild(pos[r]);rebuild(pos[l]);
	}
	
}
int query(int l,int r,int c)
{
	int res=-1;
	if (pos[l]==pos[r])
	{
		for (int i=l;i<=r;i++) if (a[i]+tag[pos[l]]<c) res=max(a[i]+tag[pos[l]],res);
		return res;
	}
	else
	{
		for (int i=l;i<=br[pos[l]];i++)
			if (a[i]+tag[pos[l]]<c) res=max(res,a[i]+tag[pos[l]]);
		for (int i=pos[l]+1;i<pos[r];i++)
		{
			auto pos=lower_bound(block[i].begin(),block[i].end(),c-tag[i]);
			if (pos!=block[i].begin()) res=max(res,*(--pos)+tag[i]);
		}
		for (int i=bl[pos[r]];i<=r;i++)
			if (a[i]+tag[pos[r]]<c) res=max(res,a[i]+tag[pos[r]]);
		return res;
	}
}
signed main()
{
	double st=clock();
	read(n);
	for (int i=1;i<=n;i++) read(a[i]);
	init();
	for (int i=1;i<=n;i++)
	{
		int opt,l,r,c,ans;
		read(opt),read(l),read(r),read(c);
		if (opt==0) add(l,r,c);
		else writewith(query(l,r,c),'\n');
	}
	return 0;
}

T4

区间加，区间和。

分块经典题。散块暴力修改，整块打 tag 标记（类似标记永久化？）。询问的时候加上 tag 标记对答案的贡献即可。

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
#define int long long
using namespace std;
template<typename T> void read(T &k)
{
	k=0;T flag=1;char b=getchar();
	while (!isdigit(b)) {flag=(b=='-')?-1:1;b=getchar();}
	while (isdigit(b)) {k=k*10+b-48;b=getchar();}
	k*=flag;
}
template<typename T> void write(T k) {if (k<0) {putchar('-'),write(-k);return;}if (k>9) write(k/10);putchar(k%10+48);}
template<typename T> void writewith(T k,char c) {write(k);putchar(c);}
const int _SIZE=5e4;
int len,bl[405],br[405],cnt;
int pos[_SIZE+5];
int n,a[_SIZE+5];
int sum[405],tag[405];
void add(int l,int r,int c)
{
	if (pos[l]==pos[r])
	{
		sum[pos[l]]+=(r-l+1)*c;
		for (int i=l;i<=r;i++) a[i]+=c;
	}
	else
	{
		for (int i=l;i<=br[pos[l]];i++) a[i]+=c;
		sum[pos[l]]+=(br[pos[l]]-l+1)*c;
		for (int i=pos[l]+1;i<pos[r];i++) tag[i]+=c;
		for (int i=bl[pos[r]];i<=r;i++) a[i]+=c;
		sum[pos[r]]+=(r-bl[pos[r]]+1)*c;
	}
}
int query(int l,int r,int c)
{
	int res=0;
	if (pos[l]==pos[r])
	{
		for (int i=l;i<=r;i++) res+=a[i]+tag[pos[l]];
		return res%c;
	}
	else
	{
		for (int i=l;i<=br[pos[l]];i++) res+=a[i]+tag[pos[l]];
		for (int i=pos[l]+1;i<pos[r];i++) res+=sum[i]+tag[i]*(br[i]-bl[i]+1);
		for (int i=bl[pos[r]];i<=r;i++) res+=a[i]+tag[pos[r]];
		return res%c;
	}
}
signed main()
{
	read(n);
	for (int i=1;i<=n;i++) read(a[i]);
	len=sqrt(n),cnt=(n-1)/len+1;
	for (int i=1;i<=cnt;i++) bl[i]=(i-1)*len+1,br[i]=min(n,i*len);
	for (int i=1;i<=cnt;i++)
		for (int j=bl[i];j<=br[i];j++)
			pos[j]=i,sum[i]+=a[j];
	for (int i=1;i<=n;i++)
	{
		int opt,l,r,c;
		read(opt),read(l),read(r),read(c);
		if (opt==0) add(l,r,c);
		else writewith(query(l,r,c+1),'\n');
	}
	return 0;
}

T5

区间开方，区间求和。

区间开方有一个很好的性质，就是一个数开不了多少方就会变成 \(1\)，而 \(1\) 和 \(0\) 无论怎么开方都是自己，不会发生改变。

根据这一性质我们可以对于开方操作暴力修改，然后如果一个块内的所有元素全部变成了 \(1\) 或 \(0\)，就给这个块打一个 tag，下次再访问到这个块时就不进行修改操作了。

时间复杂度均摊下来应该还是 \(\mathcal O(n\sqrt n)\) 的吧。

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
//#define int long long
using namespace std;
template<typename T> void read(T &k)
{
	k=0;T flag=1;char b=getchar();
	while (!isdigit(b)) {flag=(b=='-')?-1:1;b=getchar();}
	while (isdigit(b)) {k=k*10+b-48;b=getchar();}
	k*=flag;
}
template<typename T> void write(T k) {if (k<0) {putchar('-'),write(-k);return;}if (k>9) write(k/10);putchar(k%10+48);}
template<typename T> void writewith(T k,char c) {write(k);putchar(c);}
const int _SIZE=5e4,_BLOCK=1e3;
int pos[_SIZE+5],bl[_BLOCK+5],br[_BLOCK+5];
int sum[_BLOCK+5],tag[_BLOCK+5];
int a[_SIZE+5],cnt,len,n;
void init()
{
	len=sqrt(n),cnt=(n-1)/len+1;
	for (int i=1;i<=cnt;i++)
		bl[i]=(i-1)*len+1,br[i]=min(i*len,n);
	for (int i=1;i<=cnt;i++)
		for (int j=bl[i];j<=br[i];j++)
			pos[j]=i,sum[i]+=a[j];
}
void change(int id,int needChange)
{
	if (tag[id]) return;
	bool flag=1;sum[id]=0;
	for (int i=bl[id];i<=br[id];i++) 
	{
		if (needChange) a[i]=sqrt(a[i]);
		if (a[i]>1) flag=0;
		sum[id]+=a[i];
	}
	if (flag) tag[id]=1;
}
void modify(int l,int r)
{
	if (pos[l]==pos[r])
	{
		for (int i=l;i<=r;i++) a[i]=sqrt(a[i]);
		change(pos[l],0);
	}
	else
	{
		if (!tag[pos[l]])
		{
			for (int i=l;i<=br[pos[l]];i++) a[i]=sqrt(a[i]);
			change(pos[l],0);
		}
		for (int i=pos[l]+1;i<pos[r];i++) if (!tag[i]) change(i,1);
		if (!tag[pos[r]])
		{
			for (int i=bl[pos[r]];i<=r;i++) a[i]=sqrt(a[i]);
			change(pos[r],0);
		}
	}
}
int query(int l,int r)
{
	int res=0;
	if (pos[l]==pos[r])
	{
		for (int i=l;i<=r;i++) res+=a[i];
		return res;
	}
	else
	{
		for (int i=l;i<=br[pos[l]];i++) res+=a[i];
		for (int i=pos[l]+1;i<pos[r];i++) res+=sum[i];
		for (int i=bl[pos[r]];i<=r;i++) res+=a[i];
		return res;
	}
}
signed main()
{
	read(n);
	for (int i=1;i<=n;i++) read(a[i]);
	init();
	for (int i=1;i<=n;i++)
	{
		int opt,l,r,c;
		read(opt),read(l),read(r),read(c);
		if (opt==0) modify(l,r);
		else writewith(query(l,r),'\n');
		//for (int j=1;j<=n;j++) writewith(a[j],' ');puts("");
	}
	return 0;
}

T6

单点插入，随机访问。

显然的块状链表。感谢 pb_ds 库提供了 rope 容器，因此可以直接用 rope 水过这道题。

#include<bits/stdc++.h>
#include<ext/rope>
#define mem(a,b) memset(a,b,sizeof a)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
//#define int long long
using namespace std;
using namespace __gnu_cxx;
template<typename T> void read(T &k)
{
	k=0;T flag=1;char b=getchar();
	while (!isdigit(b)) {flag=(b=='-')?-1:1;b=getchar();}
	while (isdigit(b)) {k=k*10+b-48;b=getchar();}
	k*=flag;
}
template<typename T> void write(T k) {if (k<0) {putchar('-'),write(-k);return;}if (k>9) write(k/10);putchar(k%10+48);}
template<typename T> void writewith(T k,char c) {write(k);putchar(c);}
rope<int> ro;
int n;
signed main()
{
	read(n);
	for (int i=1,temp;i<=n;i++) read(temp),ro.push_back(temp);
	for (int i=1;i<=n;i++)
	{
		int opt,l,r,c;
		read(opt),read(l),read(r),read(c);
		if (opt==0) ro.insert(l-1,r);
		else writewith(ro[r-1],'\n');
	}
}

T7

区间乘，区间加，区间和。

比较麻烦。分别记录乘法和加法的 tag，访问散块的时候用类似线段树的方式下传标记，先乘后加。进行加法的时候对于散块暴力，整块加入加法的 tag。乘法的时候散块暴力，整块同时乘入加法和乘法的 tag 中。最后查询的时候把标记的贡献也加入即可。

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
//#define int long long
using namespace std;
template<typename T> void read(T &k)
{
	k=0;T flag=1;char b=getchar();
	while (!isdigit(b)) {flag=(b=='-')?-1:1;b=getchar();}
	while (isdigit(b)) {k=k*10+b-48;b=getchar();}
	k*=flag;
}
template<typename T> void write(T k) {if (k<0) {putchar('-'),write(-k);return;}if (k>9) write(k/10);putchar(k%10+48);}
template<typename T> void writewith(T k,char c) {write(k);putchar(c);}
const int _SIZE=1e5,_BLOCK=1e3,mod=10007;
int pos[_SIZE+5],bl[_BLOCK+5],br[_BLOCK+5];
int tagM[_BLOCK+5],tagA[_BLOCK+5];
int a[_SIZE+5],n,len,cnt;
void init()
{
	len=sqrt(n),cnt=(n-1)/len+1;
	for (int i=1;i<=cnt;i++) 
		bl[i]=(i-1)*len+1,br[i]=min(n,i*len);
	for (int i=1;i<=cnt;i++)
		for (int j=bl[i];j<=br[i];j++)
			pos[j]=i,tagM[i]=1;
}
void pushdown(int id)
{
	for (int i=bl[id];i<=br[id];i++)
		(a[i]=a[i]*tagM[id]+tagA[id])%=mod;
	tagM[id]=1,tagA[id]=0;
}
void add(int l,int r,int c)
{
	if (pos[l]==pos[r])
	{
		pushdown(pos[l]);
		for (int i=l;i<=r;i++) (a[i]+=c)%=mod;
	}
	else
	{
		pushdown(pos[l]);
		for (int i=l;i<=br[pos[l]];i++) (a[i]+=c)%=mod;
		for (int i=pos[l]+1;i<pos[r];i++) (tagA[i]+=c)%=mod;
		pushdown(pos[r]);
		for (int i=bl[pos[r]];i<=r;i++) (a[i]+=c)%=mod;
	}
}
void mul(int l,int r,int c)
{
	if (pos[l]==pos[r])
	{
		pushdown(pos[l]);
		for (int i=l;i<=r;i++) (a[i]*=c)%=mod;
	}
	else
	{
		pushdown(pos[l]);
		for (int i=l;i<=br[pos[l]];i++) (a[i]*=c)%=mod;
		for (int i=pos[l]+1;i<pos[r];i++)
			(tagA[i]*=c)%=mod,(tagM[i]*=c)%=mod;
		pushdown(pos[r]);
		for (int i=bl[pos[r]];i<=r;i++) (a[i]*=c)%=mod;
	}
}
int query(int x)
{
	return (a[x]*tagM[pos[x]]%mod+tagA[pos[x]])%mod;
}
signed main()
{
	read(n);
	for (int i=1;i<=n;i++) read(a[i]);
	init();
	for (int i=1;i<=n;i++)
	{
		int opt,l,r,c;
		read(opt),read(l),read(r),read(c);
		if (opt==0) add(l,r,c);
		else if (opt==1) mul(l,r,c);
		else writewith(query(r),'\n');
	}
	return 0;
}

T8

区间推平，区间查询 \(c\) 的个数。

你都区间推平了，还每次询问都推平，那我不用珂朵莉树来写真的说不过去了。

珂朵莉树支持区间推平操作，时间复杂度取决于你推平的次数。这道题推平的次数很多，因此时间复杂度是正确的，近乎 \(\mathcal O(n\log\log n)\)。

建出珂朵莉树过后直接在珂朵莉树上暴力统计即可。

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a)
//#define int long long
using namespace std;
template<typename T> void read(T &k)
{
	k=0;T flag=1;char b=getchar();
	while (!isdigit(b)) {flag=(b=='-')?-1:1;b=getchar();}
	while (isdigit(b)) {k=k*10+b-48;b=getchar();}
	k*=flag;
}
template<typename T> void write(T k) {if (k<0) {putchar('-'),write(-k);return;}if (k>9) write(k/10);putchar(k%10+48);}
template<typename T> void writewith(T k,char c) {write(k);putchar(c);}
struct Node{
	int l,r;
	mutable int v;
	Node(){}
	Node(int l,int r=0,int v=0) : l(l),r(r),v(v) {}
	bool operator< (const Node &a) const {return l<a.l;}
};
set<Node> ctlt;
auto split(int pos)
{
	auto it=ctlt.lower_bound(Node(pos));
	if (it!=ctlt.end() && it->l==pos) return it;
	it--;
	if (it->r<pos) return ctlt.end();
	int l=it->l,r=it->r,v=it->v;
	ctlt.erase(it);
	ctlt.insert(Node(l,pos-1,v));
	return ctlt.insert(Node(pos,r,v)).first;
}
void assign(int l,int r,int v)
{
	auto itr=split(r+1),itl=split(l);
	ctlt.erase(itl,itr);
	ctlt.insert(Node(l,r,v));
}
int query(int l,int r,int c)
{
	auto itr=split(r+1),itl=split(l);
	int res=0;
	for (auto it=itl;it!=itr;it++) if (it->v==c) res+=it->r-it->l+1;
	return res;
}
int n;
signed main()
{
	read(n);
	for (int i=1,temp;i<=n;i++) read(temp),ctlt.insert(Node(i,i,temp));
	for (int i=1;i<=n;i++)
	{
		int l,r,c;read(l),read(r),read(c);
		writewith(query(l,r,c),'\n');
		assign(l,r,c);
	}
	return 0;
}

T9

区间众数。

同洛谷上的蒲公英一题。先将数据离散化，然后对值域分块。

查询的时候可以得知，区间的众数只可能是中间整块的众数或者是散块的众数，只统计这两个数就行了。对于整块区间的众数可以预处理。

实现时的一些问题：查询的时候的桶数组不能用 memset 清空，因为 memset 是 \(\mathcal O(n)\) 的，所以会 T 飞。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
//#define int long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
#define mem(a,b) memset(a,b,sizeof(a));
using namespace std;
int read()
{
	int k=0,flag=1;char b=getchar();
	while (b<'0' || b>'9') {flag=(b=='-')?-1:1;b=getchar();}
	while (b>='0' && b<='9') {k=(k<<3)+(k<<1)+(b^48);b=getchar();}
	return k*flag;
}
const int _SIZE=1e5;
int n,m;
int len,sum,cnt;
int a[_SIZE+5],b[_SIZE+5];
int val[_SIZE+5],pos[_SIZE+5];
int s[1005][_SIZE+5],f[1005][1005],t[_SIZE+5];
struct BLOCK{
	int l,r;
}block[1005];
void PreWork()
{
	len=sqrt(n);
	sort(b+1,b+n+1);
	sum=unique(b+1,b+n+1)-b-1;
	cnt=(n-1)/len+1;
	for (int i=1;i<=n;i++)
		val[i]=lower_bound(b+1,b+sum+1,a[i])-b;
	for (int i=1;i<=cnt;i++)
	{
		block[i].l=(i-1)*len+1;
		block[i].r=min(n,i*len);
	}
	for (int i=1;i<=cnt;i++)
	{
		for (int j=block[i].l;j<=block[i].r;j++)
			s[i][val[j]]++,pos[j]=i;
		for (int j=1;j<=sum;j++)
			s[i][j]+=s[i-1][j];
	}
	for (int i=1;i<=cnt;i++)
		for (int j=i;j<=cnt;j++)
		{
			int most=f[i][j-1];
			for (int k=block[j].l;k<=block[j].r;k++)
			{
				int appear=s[j][val[k]]-s[i-1][val[k]],mostAppear=s[j][most]-s[i-1][most];
				//printf("%d~%d %d:%d\n",block[i].l,block[j].r,b[val[k]],appear);
				if (appear>mostAppear || (appear==mostAppear && val[k]<most))
					most=val[k];
			}
			f[i][j]=most;
		}
}
int query(int l,int r)
{
	int most=0;
	if (l>r) swap(l,r);
	if (pos[r]-pos[l]<=1)
	{
		for (int i=l;i<=r;i++)
			t[val[i]]++;
		for (int i=l;i<=r;i++)
			if (t[val[i]]>t[most] || (t[val[i]]==t[most] && val[i]<most))
				most=val[i];
		for (int i=l;i<=r;i++) t[val[i]]--;
	}
	else
	{
		for (int i=l;i<=block[pos[l]].r;i++)
			t[val[i]]++;
		for (int i=block[pos[r]].l;i<=r;i++)
			t[val[i]]++;
		most=f[pos[l]+1][pos[r]-1];
		for (int i=l;i<=block[pos[l]].r;i++)
		{
			int mostAppear=s[pos[r]-1][most]-s[pos[l]][most]+t[most];
			int currAppear=s[pos[r]-1][val[i]]-s[pos[l]][val[i]]+t[val[i]];
			if (currAppear>mostAppear || (currAppear==mostAppear && val[i]<most))
				most=val[i];
		}
		for (int i=block[pos[r]].l;i<=r;i++)
		{
			int mostAppear=s[pos[r]-1][most]-s[pos[l]][most]+t[most];
			int currAppear=s[pos[r]-1][val[i]]-s[pos[l]][val[i]]+t[val[i]];
			if (currAppear>mostAppear || (currAppear==mostAppear && val[i]<most))
				most=val[i];
		}
		for (int i=l;i<=block[pos[l]].r;i++)
			t[val[i]]--;
		for (int i=block[pos[r]].l;i<=r;i++)
			t[val[i]]--;
	}
	return b[most];
}
signed main()
{
	//freopen("P4168.in","r",stdin);
	n=read(),m=n;
	for (int i=1;i<=n;i++) a[i]=b[i]=read();
	PreWork();
	//for (int i=1;i<=cnt;i++) {printf("1~%d ",block[i].r);for (int j=1;j<=sum;j++){printf("%d:%d | ",b[j],s[i][j]);}puts("");}
	//for (int i=1;i<=cnt;i++) printf("%d~%d %d\n",block[i].l,block[i].r,b[f[i][i]]);
	int x=0;
	while (m--)
	{
		int l=read(),r=read();
		x=query(l,r);
		printf("%d\n",x);
	}
	return 0;
}

标签：10,入门,分块,LOJ,void,write,int,flag,getchar
From： https://www.cnblogs.com/hanx16msgr/p/16788758.html

LOJ 分块入门 1~9

LOJ 数列分块 \(1\sim 9\)

T1

T2

T3

T4

T5

T6

T7

T8

T9

相关文章

赞助商

阅读排行