思路都差不多，实现细节上有区别。
P5356 [Ynoi2017] 由乃打扑克 小卡常分块
点击查看代码
#include<bits/stdc++.h>
using namespace std;
namespace IO{
#define BUFSIZE 10000000
struct read{
char buf[BUFSIZE],*p1,*p2,c,f;
read():p1(buf),p2(buf){}
inline char gc(void){
return p1==p2&&(p2=buf+fread(p1=buf,1,BUFSIZE,stdin),p1==p2)?EOF:*p1++;
}
inline read& operator >>(int& x){
for(c=gc(),f=0,x=0;c!=EOF&&(c<'0'||c>'9');c=gc())if(c=='-')f=1;
if(f)for(;c>='0'&&c<='9';c=gc())x=x*10-(c-'0');
else for(;c>='0'&&c<='9';c=gc())x=x*10+(c-'0');
return *this;
}
}in;
struct write{
char buf[BUFSIZE],*p1,*p2,s[50],f;
int tp;
write():p1(buf){}
~write(){fwrite(buf,1,p1-buf,stdout);}
inline write& operator <<(int x){
if(x<0)f=1,*p1++='-';else f=0;
if(f)do{s[tp++]=-x%10+'0',x/=10;}while(x);
else do{s[tp++]=x%10+'0',x/=10;}while(x);
while(tp)*p1++=s[--tp];
return *this;
}
inline write& operator <<(char const &x){
*p1++=x;
return *this;
}
}out;
}
using IO::in;
using IO::out;
int n,m,a[100010],B,bel[100010],bcnt,L[510],R[510];
struct node{
int v,nxt1,nxt2;
node():v(),nxt1(),nxt2(){}
node(int const &x):v(x),nxt1(),nxt2(){}
node(int const &x,int const &i):v(x),nxt1(i),nxt2(){}
bool operator <(node const &x)const{return v<x.v;}
}pool[300010],*it=pool,*tr[2010];
int tag[2010],sz[2010];
inline void build(int x=1,int l=1,int r=bcnt){
if(l==r){
tr[x]=it;
for(int i=L[l];i<=R[l];i++)it[i-L[l]]=node(a[i],i);
sz[x]=R[l]-L[l]+2;
it+=sz[x]-1;
*it++=node(0x7fffffff);
std::sort(tr[x],it);
return;
}
int ls=x<<1,rs=x<<1|1,mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
static node tmp1[10010],tmp2[10010];
node *it1=tmp1,*it2=tmp2;
for(int i=0;i<sz[ls]-1;i+=10)*it1++=tr[ls][i].v;
for(int i=0;i<sz[rs]-1;i+=10)*it2++=tr[rs][i].v;
std::merge(tmp1,it1,tmp2,it2,tr[x]=it);
int &len=sz[x]=it1-tmp1+it2-tmp2+1;
it+=len-1;
*it++=node(0x7fffffff);
int i=0,j=0;
while(i<len&&j<sz[ls])if(tr[x][i].v<=tr[ls][j].v) tr[x][i++].nxt1=j;else j++;
i=0,j=0;
while(i<len&&j<sz[rs])if(tr[x][i].v<=tr[rs][j].v) tr[x][i++].nxt2=j;else j++;
}
inline void update(int pl,int pr,int k,int x=1,int l=1,int r=bcnt){
if(pl==L[l]&&pr==R[r]) return tag[x]+=k,void();
static node tmp1[10010],tmp2[10010];
node *it1=tmp1,*it2=tmp2;
if(l==r){
for(int i=0;i<sz[x]-1;i++)
if(tr[x][i].nxt1<=pr&&tr[x][i].nxt1>=pl)*it1++=node(tr[x][i].v+k,tr[x][i].nxt1);
else *it2++=node(tr[x][i].v,tr[x][i].nxt1);
*it2++=node(0x7fffffff);
std::merge(tmp1,it1,tmp2,it2,tr[x]);
return;
}
int ls=x<<1,rs=x<<1|1,mid=(l+r)>>1;
if(pr<=R[mid]) update(pl,pr,k,ls,l,mid);
else if(pl>R[mid]) update(pl,pr,k,rs,mid+1,r);
else update(pl,R[mid],k,ls,l,mid),update(R[mid]+1,pr,k,rs,mid+1,r);
for(int i=0;i<sz[ls]-1;i+=10)*it1++=tr[ls][i].v+tag[ls];
for(int i=0;i<sz[rs]-1;i+=10)*it2++=tr[rs][i].v+tag[rs];
*it2++=node(0x7fffffff);
std::merge(tmp1,it1,tmp2,it2,tr[x]);
int &len=sz[x];
int i=0,j=0;
while(i<len&&j<sz[ls]-1)if(tr[x][i].v<=tr[ls][j].v+tag[ls]) tr[x][i++].nxt1=j;else j++;
while(i<len)tr[x][i++].nxt1=sz[ls]-1;
i=0,j=0;
while(i<len&&j<sz[rs]-1)if(tr[x][i].v<=tr[rs][j].v+tag[rs]) tr[x][i++].nxt2=j;else j++;
while(i<len)tr[x][i++].nxt2=sz[rs]-1;
}
int d1[10010],d2[10010],d[20010];
int *c1;
inline void collect(int pl,int pr,int v=0,int x=1,int l=1,int r=bcnt){
if(l==r){
for(int i=0;i<sz[x];i++)
if(tr[x][i].nxt1<=pr&&tr[x][i].nxt1>=pl) *c1++=tr[x][i].v+v+tag[x];
return;
}
int ls=x<<1,rs=x<<1|1,mid=(l+r)>>1;
if(pr<=R[mid]) collect(pl,pr,v+tag[x],ls,l,mid);
else collect(pl,pr,v+tag[x],rs,mid+1,r);
}
inline int query(int pl,int pr,int v,int k,int x=1,int l=1,int r=bcnt){
while(k&&tr[x][k-1].v>v-tag[x])--k;
if(l==r) return k;
int ls=x<<1,rs=x<<1|1,mid=(l+r)>>1;
if(pr<=mid) return query(pl,pr,v-tag[x],tr[x][k].nxt1,ls,l,mid);
if(pl>mid) return query(pl,pr,v-tag[x],tr[x][k].nxt2,rs,mid+1,r);
return query(pl,mid,v-tag[x],tr[x][k].nxt1,ls,l,mid)+query(mid+1,pr,v-tag[x],tr[x][k].nxt2,rs,mid+1,r);
}
inline int getans(int pl,int pr,int k){
if(pl>pr) return 0;
return query(pl,pr,k,std::upper_bound(tr[1],tr[1]+sz[1],node(k))-tr[1]);
}
int main(){
in>>n>>m;
B=sqrt(n*log2(n));if(!B)B=1;
for(int i=1;i<=n;i++)in>>a[i],bel[i]=(i-1)/B+1;
for(int i=1;i<=n;i++)R[bel[i]]=i;
for(int i=n;i;i--)L[bel[i]]=i;
bcnt=bel[n];
build();
while(m--){
int op,l,r,k;
in>>op>>l>>r>>k;
if(op==1){
if(r-l+1<k)out<<-1;
else{
int x=0x8000000f,y=-x,ans=0,mid;
if(bel[l]==bel[r]){
c1=d,collect(l,r);
while(x<=y){
mid=(1ll*x+y)>>1;
if(std::upper_bound(d,c1,mid)-d>=k)ans=mid,y=mid-1;
else x=mid+1;
}
}else{
c1=d1,collect(l,R[bel[l]]);
c1=d2,collect(L[bel[r]],r);
std::merge(d1,d1+R[bel[l]]-l+1,d2,d2+r-L[bel[r]]+1,d);
c1=d+R[bel[l]]-l+1+r-L[bel[r]]+1;
while(x<=y){
mid=(1ll*x+y)>>1;
if(std::upper_bound(d,c1,mid)-d+getans(bel[l]+1,bel[r]-1,mid)>=k)ans=mid,y=mid-1;
else x=mid+1;
}
}
out<<ans<<'\n';
}
}else update(l,r,k);
}
return 0;
}
P4135 作诗 小清新分块
点击查看代码
#include<bits/stdc++.h>
using namespace std;
inline int rd(){
int f=1,j=0;
char w=getchar();
while(!isdigit(w)){
if(w=='-')f=-1;
w=getchar();
}
while(isdigit(w)){
j=j*10+w-'0';
w=getchar();
}
return f*j;
}
const int N=100010,M=400;
int n,q,c;
struct Datestructure{
int sum[N],num[M][M],cnt[N][M],tong[N];
int L[M],R[M],tot,K;
void init(){
K=400;
n=rd(),c=rd(),q=rd();
for(int i=1;i<=n;i++)sum[i]=rd();
for(int l=1,r;l<=n;l=r+1){
r=min(l+K-1,n);
tot++,L[tot]=l,R[tot]=r;
}
for(int i=1;i<=tot;i++){
int ansn=0;
for(int j=i;j<=tot;j++){
for(int k=L[j];k<=R[j];k++){
tong[sum[k]]++;
if(!(tong[sum[k]]&1))ansn++;
else if(tong[sum[k]]!=1)ansn--;
}
num[i][j]=ansn;
}
for(int j=L[i];j<=n;j++)tong[sum[j]]--;
}
for(int i=1;i<=tot;i++){
for(int j=L[i];j<=R[i];j++)cnt[sum[j]][i]++;
for(int j=0;j<=c;j++)cnt[j][i]+=cnt[j][i-1];
}
return ;
}
int query(int l,int r){
int lt=lower_bound(L+1,L+1+tot,l)-L;
int rt=upper_bound(R+1,R+1+tot,r)-R-1;
if(lt>=rt){
int ansn=0;
for(int i=l;i<=r;i++){
tong[sum[i]]++;
if(!(tong[sum[i]]&1))ansn++;
else if(tong[sum[i]]!=1)ansn--;
}
for(int i=l;i<=r;i++)tong[sum[i]]--;
return ansn;
}
int ansn=num[lt][rt];
for(int i=l;i<L[lt];i++){
tong[sum[i]]++;
if(!((tong[sum[i]]+cnt[sum[i]][rt]-cnt[sum[i]][lt-1])&1))ansn++;
else if((tong[sum[i]]+cnt[sum[i]][rt]-cnt[sum[i]][lt-1])!=1)ansn--;
}
for(int i=R[rt]+1;i<=r;i++){
tong[sum[i]]++;
if(!((tong[sum[i]]+cnt[sum[i]][rt]-cnt[sum[i]][lt-1])&1))ansn++;
else if((tong[sum[i]]+cnt[sum[i]][rt]-cnt[sum[i]][lt-1])!=1)ansn--;
}
for(int i=l;i<L[lt];i++)tong[sum[i]]--;
for(int i=R[rt]+1;i<=r;i++)tong[sum[i]]--;
return ansn;
}
}date;
signed main(){
date.init();
int ans=0;
for(int i=1;i<=q;i++){
int l=(rd()+ans)%n+1,r=(rd()+ans)%n+1;
if(l>r)swap(l,r);
printf("%d\n",ans=date.query(l,r));
}
return 0;
}
P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III 空间O(n)，小清新分块
点击查看代码
#include<bits/stdc++.h>
using namespace std;
inline int rd(){
int f=1,j=0;
char w=getchar();
while(!isdigit(w)){
if(w=='-')f=-1;
w=getchar();
}
while(isdigit(w)){
j=j*10+w-'0';
w=getchar();
}
return f*j;
}
const int N=5e5+10,block=720;
int a[N],lsh[N],at[N],belong[N],cnt[N],f[block][block],n,m,last;
vector<int>in[N];
struct Block{
int l,r;
}b[block];
inline int ask(int l,int r){
int bl=belong[l],br=belong[r],ans=0;
if(bl==br){
for(int i=l;i<=r;i++){
ans=max(ans,++cnt[a[i]]);
}
for(int i=l;i<=r;i++){
cnt[a[i]]=0;
}
}else{
ans=f[bl+1][br-1];
for(int i=l;i<=b[bl].r;i++){
for(int pos=at[i];pos+ans<in[a[i]].size()&&in[a[i]][pos+ans]<=r;ans++);
}
for(int i=b[br].l;i<=r;i++){
for(int pos=at[i];pos-ans>=0&&in[a[i]][pos-ans]>=l;ans++);
}
}
return ans;
}
int main(){
n=rd(),m=rd();
for(int i=1;i<=n;i++){
a[i]=lsh[i]=rd();
}
sort(lsh+1,lsh+n+1);
int sz=unique(lsh+1,lsh+n+1)-lsh;
for(int i=1;i<=n;i++){
a[i]=lower_bound(lsh+1,lsh+sz,a[i])-lsh;
in[a[i]].push_back(i);
at[i]=in[a[i]].size()-1;
}
int c=0;
for(int i=1;i<=n;i+=block){
c++;
b[c].l=i;
b[c].r=min(i+block-1,n);
}
for(int i=1;i<=c;i++){
int ans=0;
for(int j=b[i].l;j<=b[i].r;j++){
belong[j]=i;
}
for(int j=i;j<=c;j++){
for(int k=b[j].l;k<=b[j].r;k++){
ans=max(ans,++cnt[a[k]]);
}
f[i][j]=ans;
}
for(int j=i;j<=c;j++){
for(int k=b[j].l;k<=b[j].r;k++){
cnt[a[k]]=0;
}
}
}
int fans=0;
while(m--){
int l=rd()^fans,r=rd()^fans;
printf("%d\n",fans=ask(l,r));
}
return 0;
}
P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I 小清新分块，区间众数
没写，咕咕咕