P3203 [HNOI2010] 弹飞绵羊
记录每个位置跳出当前块所需要的步数和跳出的位置。
从后往前统计
#include<bits/stdc++.h>
#define maxn 200100
using namespace std;
int n,m,len;
int pos[maxn],k[maxn];
int nxt[maxn],stp[maxn];
struct fk{int l,r;}a[maxn];
int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
return s*w;
}
void init(){
len=sqrt(n);
for(int i=0;i<n;i++) pos[i]=i/len;
for(int i=0;i<=pos[n-1];i++){
a[i].l=i*len;
a[i].r=(i+1)*len-1;
}
a[pos[n-1]].r=n-1;
}
void work(int l,int r){
for(int i=r;i>=l;i--){
if(i+k[i]>a[pos[i]].r){
nxt[i]=i+k[i];
stp[i]=1;
}
else{
nxt[i]=nxt[i+k[i]];
stp[i]=stp[i+k[i]]+1;
}
}
}
int main(){
n=read();
for(int i=0;i<n;i++) k[i]=read();
init();work(0,n-1);m=read();
for(int i=1,opt,x,y,ans,p;i<=m;i++){
opt=read();x=read();
if(opt==1){
p=x,ans=0;
while(p<n) ans+=stp[p],p=nxt[p];
cout<<ans<<endl;
}
else{
y=read();k[x]=y;
work(a[pos[x]].l,a[pos[x]].r);
}
}
return 0;
}
P4168 [Violet] 蒲公英
存下每种颜色出现的位置,处理块与块中的众数。
注意离散化。
计数时,中间的块直接记录,两边零散位置暴力扫。
#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
int n,id,l,r,sum,res,m,las,o;
int a[maxn],num[maxn],pos[maxn];
int cnt[maxn],f[3010][3010],b[maxn];
vector<int>l1[maxn];
map<int,int>mp;
int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
return s*w;
}
int getans(int ll,int rr,int x){
return upper_bound(l1[x].begin(),l1[x].end(),rr)-lower_bound(l1[x].begin(),l1[x].end(),ll);
}
void init(int x){
memset(cnt,0,sizeof(cnt));
int maxx=0,num1=0;
for(int i=(x-1)*m+1;i<=n;i++){
cnt[a[i]]++;
if(cnt[a[i]]>maxx||(cnt[a[i]]==maxx&&a[i]<num1))
maxx=cnt[a[i]],num1=a[i];
f[x][pos[i]]=num1;
}
}
int ask(int l1,int r1){
int maxx=0,num1=0;
if(pos[l1]+1<pos[r1])
maxx=getans(l1,r1,f[pos[l1]+1][pos[r1]-1]),num1=f[pos[l1]+1][pos[r1]-1];
for(int i=l1;i<=min(r1,pos[l1]*m);i++) {
res=getans(l1,r1,a[i]);
if(res>maxx||(res==maxx&&a[i]<num1))
maxx=res,num1=a[i];
}
if(pos[l1]!=pos[r1]){
for(int i=(pos[r1]-1)*m+1;i<=r1;i++){
res=getans(l1,r1,a[i]);
if(res>maxx||(res==maxx&&a[i]<num1))
maxx=res,num1=a[i];
}
}
return num[num1];
}
int main(){
n=read();o=read();
for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];
sort(b+1,b+n+1);
for(int i=1;i<=n;i++) if(!mp[b[i]])
id++,mp[b[i]]=id,num[id]=b[i];
for(int i=1;i<=n;i++)
a[i]=mp[a[i]],l1[a[i]].push_back(i);
for(int i=1;i<=id;i++) l1[i].push_back(n+1);
m=sqrt(n);
for(int i=1;i<=n;i++) pos[i]=(i-1)/m+1;
sum=pos[n];
for(int i=1;i<=sum;i++) init(i);
for(int i=1;i<=o;i++){
l=read();r=read();
l=(l+las-1)%n+1,r=(r+las-1)%n+1;
if(l>r) swap(l,r);las=ask(l,r);
cout<<las<<endl;
}
return 0;
}
标签:maxx,ch,分块,int,2024,maxn,补题,&&,getchar
From: https://www.cnblogs.com/KnightL/p/18115332