分块
P2801 教主的魔法
分块即可，复制一个数组保持块内有序，然后用一个数组记录块整体的加减情况，就可以了。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int n,x,m,q;
int a[N],b[N];
struct node{
int st,ed,tag;
}k[N];
void change(int l,int r,int w){
int lx=(l-1)/x+1,rx=(r-1)/x+1;
if(lx==rx){
for(int i=l;i<=r;i++) a[i]+=w;
for(int i=k[lx].st;i<=k[lx].ed;i++) b[i]=a[i];
sort(b+k[lx].st,b+k[lx].ed+1);
return;
}
for(int i=l;i<=k[lx].ed;i++) a[i]+=w;
for(int i=k[lx].st;i<=k[lx].ed;i++) b[i]=a[i];
sort(b+k[lx].st,b+k[lx].ed+1);
for(int i=k[rx].st;i<=r;i++) a[i]+=w;
for(int i=k[rx].st;i<=k[rx].ed;i++) b[i]=a[i];
sort(b+k[rx].st,b+k[rx].ed+1);
for(int i=lx+1;i<rx;i++) k[i].tag+=w;
}
int query(int l,int r,int c){
int res=0;
int lx=(l-1)/x+1,rx=(r-1)/x+1;
if(lx==rx){
for(int i=l;i<=r;i++) if(a[i]+k[lx].tag>=c) res++;
return res;
}
for(int i=l;i<=k[lx].ed;i++) if(a[i]+k[lx].tag>=c) res++;
for(int i=k[rx].st;i<=r;i++) if(a[i]+k[rx].tag>=c) res++;
for(int i=lx+1;i<rx;i++){
int id=lower_bound(b+k[i].st,b+k[i].ed+1,c-k[i].tag)-b;
if(id>=k[i].st&&id<=k[i].ed) res+=k[i].ed-id+1;
}
return res;
}
signed main(){
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
x=sqrt(1.0*n);
m=ceil(1.0*n/(1.0*x));
for(int i=1;i<=m;i++){
k[i].st=(i-1)*x+1,k[i].ed=min(i*x,n);
sort(b+k[i].st,b+k[i].ed+1);
}
while(q--){
char op;
int l,r,w;
cin>>op>>l>>r>>w;
if(op=='M') change(l,r,w);
else cout<<query(l,r,w)<<"\n";
}
return 0;
}P4168 [Violet] 蒲公英
预处理一下每两个块之间的众数以及前几个块每个值的个数，
先算出中间块的众数加上两边相等的数量，在看两边散块的值加上中间的值是否比当前答案大，都可以用预处理来的数据计算。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+5;
const int M=sqrt(N)+3;
int n,x,m,q,ans;
int a[N],b[N];
int cnt[N],f[M][N],g[M][M];
struct node{int st,ed;} k[N];
void init(){
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++) f[i][j]=f[i-1][j];
for(int j=k[i].st;j<=k[i].ed;j++) f[i][a[j]]++;
}
for(int i=1;i<=m;i++){
memset(cnt,0,sizeof cnt);
int res=0,sum=0;
for(int i2=i;i2<=m;i2++){
for(int j=k[i2].st;j<=k[i2].ed;j++){
cnt[a[j]]++;
if(cnt[a[j]]>sum||(cnt[a[j]]==sum&&a[j]<res)) res=a[j],sum=cnt[a[j]];
}
g[i][i2]=res;
}
}
memset(cnt,0,sizeof cnt);
}
int query(int l,int r){
int lx=(l-1)/x+1,rx=(r-1)/x+1;
if(rx-lx<=1){
int res=0;
for(int i=l;i<=r;i++) cnt[a[i]]=0;
for(int i=l;i<=r;i++){
cnt[a[i]]++;
if(cnt[a[i]]>cnt[res]||(cnt[a[i]]==cnt[res]&&a[i]<res)) res=a[i];
}
return res;
}
int res=g[lx+1][rx-1];
int sum=f[rx-1][res]-f[lx][res];
for(int i=l;i<=k[lx].ed;i++) sum+=(a[i]==res),cnt[a[i]]=0;
for(int i=k[rx].st;i<=r;i++) sum+=(a[i]==res),cnt[a[i]]=0;
for(int i=l;i<=k[lx].ed;i++) cnt[a[i]]++;
for(int i=k[rx].st;i<=r;i++) cnt[a[i]]++;
for(int i=l;i<=k[lx].ed;i++){
int tot=f[rx-1][a[i]]-f[lx][a[i]]+cnt[a[i]];
if(tot>sum||(tot==sum&&a[i]<res)) sum=tot,res=a[i];
}
for(int i=k[rx].st;i<=r;i++){
int tot=f[rx-1][a[i]]-f[lx][a[i]]+cnt[a[i]];
if(tot>sum||(tot==sum&&a[i]<res)) sum=tot,res=a[i];
}
return res;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>b[i],a[i]=b[i];
sort(b+1,b+1+n);
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
x=sqrt(1.0*n);
m=(n+x-1)/x;
for(int i=1;i<=m;i++) k[i].st=(i-1)*x+1,k[i].ed=min(i*x,n);
init();
for(int i=1;i<=n;i++){
int l,r;
cin>>l>>r;
ans=b[query(l,r)];
cout<<ans<<"\n";
}
return 0;
}P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III
用一个数组表示每两个块之间众数的个数，一个 vector 表示每个值在原数组的下标，一个数组表示当前数在 vector 的下标。
答案先暂定为中间块的众数，然后再扫两边的散块，vector 往前或往后一个一个扫下标，直到超出左右两边的边界。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5,M=720;
int n,x,m,q,ans;
int a[N],b[N];
int in[N],st[M],ed[M];
int f[M][M],pos[N],cnt[N];
vector<int> p[N];
void init(){
x=sqrt(1.0*n),m=(n+x-1)/x;
sort(b+1,b+1+n);
for(int i=1;i<=n;i++){
in[i]=(i-1)/x+1;
a[i]=lower_bound(b+1,b+1+n,a[i])-b;
p[a[i]].push_back(i);
pos[i]=p[a[i]].size()-1;
}
for(int i=1;i<=m;i++) st[i]=(i-1)*x+1,ed[i]=min(i*x,n);
for(int i=1;i<=m;i++){
memset(cnt,0,sizeof cnt);
for(int j=i;j<=m;j++){
f[i][j]=f[i][j-1];
for(int k=st[j];k<=ed[j];k++) f[i][j]=max(f[i][j],++cnt[a[k]]);
}
}
}
int query(int l,int r){
if(l>r||l>n) return 0;
l=max(1ll,l),r=min(n,r);
int ans=-1;
if(in[l]==in[r]){
for(int i=l;i<=r;i++) cnt[a[i]]=0;
for(int i=l;i<=r;i++) ans=max(ans,++cnt[a[i]]);
return ans;
}
ans=f[in[l]+1][in[r]-1];
for(int i=l;i<=ed[in[l]];i++) while(pos[i]+ans<p[a[i]].size()&&p[a[i]][pos[i]+ans]<=r) ans++;
for(int i=r;i>=st[in[r]];i--) while(pos[i]-ans>=0&&p[a[i]][pos[i]-ans]>=l) ans++;
return ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>b[i],a[i]=b[i];
init();
while(q--){
int l,r;
cin>>l>>r;
l^=ans,r^=ans;
ans=query(l,r);
cout<<ans<<"\n";
}
return 0;
}P4135 作诗
预处理前几个块每个值出现的次数、以及每两个块之间出现偶数次数的个数，
对于每次询问，枚举两边的散块，看是否会对中间块出现次数产生影响，对答案进行相应的加减即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,M=720;
int n,x,c,m,q,ans;
int a[N],b[N];
int cnt[N],tag[N],f[M][N],g[M][M];
struct node{int st,ed;} k[N];
void init(){
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++) f[i][j]=f[i-1][j];
for(int j=k[i].st;j<=k[i].ed;j++) f[i][a[j]]++;
}
for(int i=1;i<=m;i++){
memset(cnt,0,sizeof cnt);
for(int i2=i;i2<=m;i2++){
g[i][i2]=g[i][i2-1];
for(int j=k[i2].st;j<=k[i2].ed;j++){
cnt[a[j]]++;
if(cnt[a[j]]%2==0) g[i][i2]++;
else if(cnt[a[j]]>1) g[i][i2]--;
}
}
}
}
int query(int l,int r){
int lx=(l-1)/x+1,rx=(r-1)/x+1;
if(rx-lx<=1){
int res=0;
for(int i=l;i<=r;i++) cnt[a[i]]=0;
for(int i=l;i<=r;i++){
cnt[a[i]]++;
if(cnt[a[i]]%2==0) res++;
else if(cnt[a[i]]>1) res--;
}
return res;
}
int res=g[lx+1][rx-1];
vector<int> vc;
for(int i=l;i<=k[lx].ed;i++) tag[a[i]]=cnt[a[i]]=0;
for(int i=k[rx].st;i<=r;i++) tag[a[i]]=cnt[a[i]]=0;
for(int i=l;i<=k[lx].ed;i++) cnt[a[i]]++,vc.push_back(a[i]);
for(int i=k[rx].st;i<=r;i++) cnt[a[i]]++,vc.push_back(a[i]);
for(int i=0;i<vc.size();i++){
int v=vc[i];
if(tag[v]) continue;
tag[v]=1;
if(cnt[v]%2==1&&(f[rx-1][v]-f[lx][v])%2==1) res++;
if((cnt[v]%2)==0&&(f[rx-1][v]-f[lx][v])==0) res++;
if(cnt[v]%2==1&&(f[rx-1][v]-f[lx][v])%2==0&&f[rx-1][v]-f[lx][v]>0) res--;
}
return res;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>c>>q;
for(int i=1;i<=n;i++) cin>>b[i],a[i]=b[i];
sort(b+1,b+1+n);
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
x=sqrt(1.0*n);
m=(n+x-1)/x;
for(int i=1;i<=m;i++) k[i].st=(i-1)*x+1,k[i].ed=min(i*x,n);
init();
while(q--){
int l,r;
cin>>l>>r;
l=(l+ans)%n+1,r=(r+ans)%n+1;
if(l>r) swap(l,r);
ans=query(l,r);
cout<<ans<<"\n";
}
return 0;
}P5356 [Ynoi Easy Round 2017] 由乃打扑克
区间加的操作不必多说，
对于查询区间第 大，我们二分答案，check 函数显然就应该是查询区间内小于等于 mid 的个数与 作比较，还是比较好写的。
但是光这样写会 TLE，要在查询区间小于等于某个数的个数时，对于中间的整块，加上特判，能不二分的就不二分，可以做到优化。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,x,m,q;
int a[N],b[N];
struct node{
int st,ed,tag;
}k[N];
void change(int l,int r,int w){
int lx=(l-1)/x+1,rx=(r-1)/x+1;
if(lx==rx){
for(int i=l;i<=r;i++) a[i]+=w;
for(int i=k[lx].st;i<=k[lx].ed;i++) b[i]=a[i];
sort(b+k[lx].st,b+k[lx].ed+1);
return;
}
for(int i=l;i<=k[lx].ed;i++) a[i]+=w;
for(int i=k[lx].st;i<=k[lx].ed;i++) b[i]=a[i];
sort(b+k[lx].st,b+k[lx].ed+1);
for(int i=k[rx].st;i<=r;i++) a[i]+=w;
for(int i=k[rx].st;i<=k[rx].ed;i++) b[i]=a[i];
sort(b+k[rx].st,b+k[rx].ed+1);
for(int i=lx+1;i<rx;i++) k[i].tag+=w;
}
int query(int l,int r,int c){//<=c的个数
int res=0;
int lx=(l-1)/x+1,rx=(r-1)/x+1;
if(lx==rx){
for(int i=l;i<=r;i++) if(a[i]+k[lx].tag<=c) res++;
return res;
}
for(int i=l;i<=k[lx].ed;i++) if(a[i]+k[lx].tag<=c) res++;
for(int i=k[rx].st;i<=r;i++) if(a[i]+k[rx].tag<=c) res++;
for(int i=lx+1;i<rx;i++){
if(c<b[k[i].st]+k[i].tag) continue;
if(c>=b[k[i].ed]+k[i].tag) {
res+=k[i].ed-k[i].st+1;
continue;
}
int id=upper_bound(b+k[i].st,b+k[i].ed+1,c-k[i].tag)-b;
if(id>=k[i].st&&id<=k[i].ed) res+=id-k[i].st;
}
return res;
}
int getmin(int l,int r){
int res=LONG_LONG_MAX;
int lx=(l-1)/x+1,rx=(r-1)/x+1;
if(lx==rx){
for(int i=l;i<=r;i++) res=min(res,a[i]+k[lx].tag);
return res;
}
for(int i=l;i<=k[lx].ed;i++) res=min(res,a[i]+k[lx].tag);
for(int i=k[rx].st;i<=r;i++) res=min(res,a[i]+k[rx].tag);
for(int i=lx+1;i<rx;i++) res=min(res,b[k[i].st]+k[i].tag);
return res;
}
int getmax(int l,int r){
int res=LONG_LONG_MIN;
int lx=(l-1)/x+1,rx=(r-1)/x+1;
if(lx==rx){
for(int i=l;i<=r;i++) res=max(res,a[i]+k[lx].tag);
return res;
}
for(int i=l;i<=k[lx].ed;i++) res=max(res,a[i]+k[lx].tag);
for(int i=k[rx].st;i<=r;i++) res=max(res,a[i]+k[rx].tag);
for(int i=lx+1;i<rx;i++) res=max(res,b[k[i].ed]+k[i].tag);
return res;
}
inline int get(int x,int y,int k){
if(k<1||k>y-x+1) return -1;
int l=getmin(x,y),r=getmax(x,y),res=-1;
while(l<=r){
int mid=l+r>>1;
if(query(x,y,mid)<k) l=mid+1;
else{
r=mid-1;
res=mid;
}
}
return res;
}
signed main(){
ios::sync_with_stdio(0);
cout.tie(0),cin.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
x=sqrt(1.0*n);
m=ceil(1.0*n/(1.0*x));
for(int i=1;i<=m;i++){
k[i].st=(i-1)*x+1,k[i].ed=min(i*x,n);
sort(b+k[i].st,b+k[i].ed+1);
}
while(q--){
int op,l,r,w;
cin>>op>>l>>r>>w;
if(op==2) change(l,r,w);
else cout<<get(l,r,w)<<"\n";
}
return 0;
}P3863 序列
考虑把时间看成一个数组，存储的是每个时间点当前数组某个数被加上了多少，并按顺序枚举原数组，
这个时候再对输入离线处理，区间加就可以看作是差分，考虑区间加对这个时间以后的所有时间都会产生影响，那就应该是对时间数组进行区间加，分块处理即可。
查询就相当于询问当前点的时间数组的一个区间内有多少数大于或等于 。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,M=720;
int n,x,m,q,idx;
int A[N],a[N],b[N],sum[M],st[M],ed[M],ans[N];
struct tag{
int op,v,t;
bool operator<(const tag b){
return t<b.t;
}
};
vector<tag> ve[N];
void add(int l,int r,int k){
int lx=(l-1)/x+1,rx=(r-1)/x+1;
if(lx==rx){
for(int i=l;i<=r;i++) a[i]+=k;
for(int i=st[lx];i<=ed[lx];i++) b[i]=a[i];
sort(b+st[lx],b+ed[lx]+1);
return;
}
for(int i=l;i<=ed[lx];i++) a[i]+=k;
for(int i=st[lx];i<=ed[lx];i++) b[i]=a[i];
sort(b+st[lx],b+ed[lx]+1);
for(int i=st[rx];i<=r;i++) a[i]+=k;
for(int i=st[rx];i<=ed[rx];i++) b[i]=a[i];
sort(b+st[rx],b+ed[rx]+1);
for(int i=lx+1;i<rx;i++) sum[i]+=k;
}
int query(int l,int r,int k){
int ans=0;
int lx=(l-1)/x+1,rx=(r-1)/x+1;
if(lx==rx){
for(int i=l;i<=r;i++) if(a[i]+sum[lx]>=k) ans++;
return ans;
}
for(int i=l;i<=ed[lx];i++) if(a[i]+sum[lx]>=k) ans++;
for(int i=st[rx];i<=r;i++) if(a[i]+sum[rx]>=k) ans++;
for(int i=lx+1;i<rx;i++){
int pos=lower_bound(b+st[i],b+ed[i]+1,k-sum[i])-b;
if(pos>=st[i]&&pos<=ed[i]) ans+=ed[i]-pos+1;
}
return ans;
}
signed main(){
memset(ans,-1,sizeof ans);
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>A[i];
x=sqrt(1.0*q);
m=(q+x-1)/x;
for(int i=1;i<=m;i++) st[i]=(i-1)*x+1,ed[i]=min(i*x,q);
for(int i=1;i<=q;i++){
int opt,l,r,x;
cin>>opt;
if(opt==1){
cin>>l>>r>>x;
ve[l].push_back({1,x,i});
ve[r+1].push_back({1,-x,i});
}
else{
cin>>l>>r;
ve[l].push_back({2,r,i});
}
}
for(int i=1;i<=n;i++){
sort(ve[i].begin(),ve[i].end());
for(int j=0;j<ve[i].size();j++){
tag u=ve[i][j];
int op=u.op,t=u.t,v=u.v;
if(op==1) add(t,q,v);
else ans[t]=query(0,t-1,v-A[i]);
}
}
for(int i=1;i<=q;i++) if(ans[i]!=-1) cout<<ans[i]<<"\n";
return 0;
}P10590 磁力块
考虑 BFS，每次新加入点时，需要判断是否满足一个二位偏序关系，
第一维直接排序，第二维直接分块维护即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define dis(X1,Y1,X2,Y2) (X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)
const int N=1e6+5;
const int M=1e3+5;
int n,x,m,q,ans;
int st[M],ed[M],tag[N],mx[M];
struct node{
int d,m,p,r;
}a[N];
queue<int> qu;
bool cmpm(node A,node B){return A.m<B.m;}
bool cmpd(node A,node B){return A.d<B.d;}
void init(){
x=sqrt(1.0*n);
m=ceil(1.0*n/(1.0*x));
for(int i=1;i<=m;i++){
st[i]=(i-1)*x+1,ed[i]=min(i*x,n);
mx[i]=a[ed[i]].m;
sort(a+st[i],a+ed[i]+1,cmpd);
}
}
void add(int p,int r){
for(int i=1;i<=m;i++){
if(mx[i]<=p){
while(st[i]<=ed[i]&&a[st[i]].d<=r){
if(!tag[st[i]]){
qu.push(st[i]);
ans++;
tag[st[i]]=1;
}
st[i]++;
}
}
else{
for(int j=st[i];j<=ed[i];j++){
if(!tag[j]&&a[j].d<=r&&a[j].m<=p){
qu.push(j);
ans++;
tag[j]=1;
}
}
break;
}
}
}
signed main(){
int x0,y0,p0,r0;
cin>>x0>>y0>>p0>>r0>>n;
r0=r0*r0;
for(int i=1;i<=n;i++){
int x1,y1;
cin>>x1>>y1>>a[i].m>>a[i].p>>a[i].r;
a[i].r=a[i].r*a[i].r;
a[i].d=dis(x1,y1,x0,y0);
}
a[0]={0,0,p0,r0};
sort(a+1,a+1+n,cmpm);
init();
qu.push(0);
while(qu.size()){
int id=qu.front();
qu.pop();
add(a[id].p,a[id].r);
}
cout<<ans;
return 0;
}P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I
分块，预处理块内逆序对 $pr[i]$、$su[i]$，块间前缀和 $s[id][x]$ 记录前 $id$ 块中 $\le x$ 的个数，以及块间逆序对 $t[i][j]$。查询时根据 $l,r$ 是否同块分类处理：同块用预处理的 $g$ 数组直接计算，不同块则分别计算左块、右块、中间块的贡献，用双指针合并左右零散部分，最后加上 $pr[r]$ 和 $su[l]$ 得到答案，复杂度 $O(\sqrt{n})$ 每次。
搞笑的是这题卡常，相同的代码我交了 16 发终于过了。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,M=350,B=300;
int n,m,q,ans;
int a[N],b[N],pr[N],su[N],ts[N];
int st[M],ed[M],be[N],po[N];
int s[M][N],g[M][N],t[M][M];
int w[N],w2[N],a1[N],sm[N],is[N];
struct node{
int id,x;
bool operator <(const node &j) const {
return x<j.x;
}
}c[N];
int read(){
int x=0,f=1;char ch=getchar_unlocked();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar_unlocked();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar_unlocked();}
return x*f;
}
void up(int x,int k){
for(int i=be[x];i<=be[n];i++) sm[i]+=k;
for(int i=x;i<=ed[be[x]];i++) is[i]+=k;
}
inline int qu(int x){return sm[be[x]-1]+is[x];}
void pre(int id){
int tp=0;
for(int i=st[id];i<=ed[id];i++) w[++tp]=a[i];
sort(w+1,w+tp+1);
for(int i=1,j=0;i<=n;i++){
while(j<tp && w[j+1]<c[i].x) j++;
s[id][c[i].id]=j;
}
for(int i=st[id];i<=ed[id];i++) a1[i]=w[i-st[id]+1];
for(int i=ed[id]+1;i>st[id];i--){
if(i<=ed[id]) up(a[i],1);
for(int j=st[id];j<i;j++) g[i-st[id]-1][j]=ts[j]-sm[be[a[j]]-1]-is[a[j]];
}
for(int i=1,j;i<=be[n];i++){
sm[i]=0;
j=ed[i];
while(is[j]) is[j--]=0;
}
}
int qry(int l,int r){
int ret=0;
if(be[l]==be[r]){
for(int i=l;i<=r;i++) ret+=g[r-st[be[l]]][i];
return ret;
}
int t1=0,t2=0;
for(int i=st[be[l]];i<=ed[be[l]];i++) if(po[a1[i]]>=l) w[++t1]=a1[i];
for(int i=st[be[r]];i<=ed[be[r]];i++) if(po[a1[i]]<=r) w2[++t2]=a1[i];
for(int i=1,j=0;i<=t1;i++){
while(j<t2 && w2[j+1]<w[i]) j++;
ret+=j;
}
for(int i=l;i<=ed[be[l]];i++) ret+=s[be[r]-1][i]-s[be[l]][i];
for(int i=st[be[r]];i<=r;i++) ret+=(st[be[r]]-ed[be[l]]-1)-(s[be[r]-1][i]-s[be[l]][i]);
for(int i=be[l]+1;i<be[r];i++) ret+=t[i][be[r]-1]-t[i][i]+pr[ed[i]];
return ret+pr[r]+su[l];
}
void init(){
for(int i=1;i<=n;i++){
be[i]=i/B+1;
ed[be[i]]=i;
}
for(int i=n;i>=1;i--) st[be[i]]=i;
for(int i=1;i<=be[n];i++){
for(int j=st[i];j<=ed[i];j++){
pr[j]=(j==st[i]?0:pr[j-1])+(j-st[i])-qu(a[j]);
up(a[j],1);
}
for(int j=st[i];j<=ed[i];j++) up(a[j],-1);
for(int j=ed[i];j>=st[i];j--){
su[j]=(j==ed[i]?0:su[j+1])+(ts[j]=qu(a[j]));
up(a[j],1);
}
for(int j=ed[i];j>=st[i];j--) up(a[j],-1);
}
for(int i=1;i<=be[n];i++) pre(i);
for(int j=1;j<=be[n];j++){
for(int i=1;i<=n;i++){
s[j][i]+=s[j-1][i];
t[be[i]][j]+=s[j][i];
}
}
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;i++){
a[i]=read();
c[i]={i,a[i]};
po[a[i]]=i;
}
sort(c+1,c+n+1);
init();
int l,r,la=0;
for(int i=1;i<=m;i++){
l=read(),r=read();
l^=la,r^=la;
la=qry(l,r);
cout<<la<<"\n";
}
return 0;
}P6177 【模板】树分块 / Count on a tree II
模板，树剖+分块。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e4+5,M=2e2+5;
int n,q,x,m,cnt;
int idx;
int vis[N],a[N],b[N];
int fa[N],siz[N],top[N],son[N],dep[N],dfn[N];
int st[M],ed[M];
vector<int> t[N];
bitset<N> ans,f[M][M];
void dfs1(int u,int f){
fa[u]=f,dep[u]=dep[f]+1,siz[u]=1;
for(int v:t[u]){
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int topf){
dfn[u]=++idx,top[u]=topf;
if(!son[u]) return;
dfs2(son[u],topf);
for(int v:t[u]){
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
void init(){
x=sqrt(n*1.0),m=(n+x-1)/x;
for(int i=1;i<=m;i++){
st[i]=(i-1)*x+1,ed[i]=min(n,i*x);
for(int j=st[i];j<=ed[i];j++) f[i][i].set(vis[j]);
}
for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++) f[i][j]=f[i][j-1]|f[j][j];
}
void add(int l,int r){
int lx=(l-1)/x+1,rx=(r-1)/x+1;
if(lx==rx){
for(int i=l;i<=r;i++) ans.set(vis[i]);
return;
}
ans|=f[lx+1][rx-1];
for(int i=l;i<=ed[lx];i++) ans.set(vis[i]);
for(int i=st[rx];i<=r;i++) ans.set(vis[i]);
}
void get(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
add(dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
add(dfn[x],dfn[y]);
}
signed main(){
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
t[u].push_back(v);
t[v].push_back(u);
}
sort(b+1,b+1+n);
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=n;i++) vis[dfn[i]]=a[i];
init();
while(q--){
int l,r;
cin>>l>>r;
l^=ans.count();
ans.reset();
get(l,r);
cout<<ans.count()<<"\n";
}
return 0;
}P3603 雪辉
首先观察到值域可以直接存下了，所以直接按照上一题的写法，答案的 bitset 取反后用一个 _Find_first 函数就结束了。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,B=1000,V=30005;
int n,m,yf,lans,M;
int w[N],vis[N];
int st[105],ed[105];
int fa[N],dep[N],siz[N],son[N],top[N],dfn[N],idx;
vector<int> t[N];
bitset<V> f[105][105],ans;
void dfs1(int u,int f){
fa[u]=f,dep[u]=dep[f]+1,siz[u]=1;
for(int v:t[u]){
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int topf){
dfn[u]=++idx,top[u]=topf;
if(!son[u]) return;
dfs2(son[u],topf);
for(int v:t[u]){
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
void init(){
M=(n+B-1)/B;
for(int i=1;i<=M;i++){
st[i]=(i-1)*B+1;
ed[i]=min(n,i*B);
for(int j=st[i];j<=ed[i];j++)
f[i][i].set(vis[j]);
}
for(int i=1;i<=M;i++)
for(int j=i+1;j<=M;j++)
f[i][j]=f[i][j-1]|f[j][j];
}
void add(int l,int r){
int bl=(l-1)/B+1,br=(r-1)/B+1;
if(bl==br){
for(int i=l;i<=r;i++) ans.set(vis[i]);
return;
}
if(bl+1<=br-1) ans|=f[bl+1][br-1];
for(int i=l;i<=ed[bl];i++) ans.set(vis[i]);
for(int i=st[br];i<=r;i++) ans.set(vis[i]);
}
void get(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
add(dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
add(dfn[x],dfn[y]);
}
signed main(){
cin>>n>>m>>yf;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
t[u].push_back(v);
t[v].push_back(u);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=n;i++) vis[dfn[i]]=w[i];
init();
lans=0;
while(m--){
int a;
cin>>a;
vector<pair<int,int>> bian;
for(int i=1;i<=a;i++){
int x,y;
cin>>x>>y;
if(yf){
x^=lans;
y^=lans;
}
bian.emplace_back(x,y);
}
ans.reset();
for(auto[x,y]:bian) get(x,y);
int cnt=ans.count();
int mex=(~ans)._Find_first();
cout<<cnt<<" "<<mex<<"\n";
lans=cnt+mex;
}
return 0;
}P2325 [SCOI2005] 王室联邦
观察到省会可以在省外，那就可以乱搞一通了！！！
枚举子树节点，每满 个点就分成一个小块，这样一个块内最多 个点。
最后肯定最多剩余 个块，加上剩余的块最多 个点，符合题意。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+5;
int n,b,idx;
int in[N],cap[N];
vector<int> t[N];
stack<int> s;
void dfs(int u,int fa){
int st=s.size();
for(int v:t[u]){
if(v==fa) continue;
dfs(v,u);
if(s.size()-st>=b){
cap[++idx]=u;
while(s.size()>st){
in[s.top()]=idx;
s.pop();
}
}
}
s.push(u);
}
signed main(){
cin>>n>>b;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
t[u].push_back(v);
t[v].push_back(u);
}
dfs(1,0);
if(idx==0) idx=1,in[1]=1,cap[1]=1;
while(s.size()){
in[s.top()]=idx;
s.pop();
}
cout<<idx<<"\n";
for(int i=1;i<=n;i++) cout<<in[i]<<" ";
cout<<"\n";
for(int i=1;i<=idx;i++) cout<<cap[i]<<" ";
return 0;
}P12511 [集训队互测 2024] 树上简单求和
把两个树都树剖映射成两个序列，就变成了区间加上一个排列，并区间查询。
对两个序列分块，分四种散块和整块关系讨论，具体的操作看代码：
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N=2e5+5;
const int M=sqrt(N)+5;
int n,q,bs,m;
int vis[N],p[N],invp[N];
int st[M],ed[M],in[N];
int ltr[N],tag[M],sum[M],cnt[M][M];
struct tree{
vector<int> t[N];
int idx=0;
int fa[N],son[N],siz[N],dep[N],top[N],dfn[N];
inline void add(int u,int v){t[u].push_back(v),t[v].push_back(u);}
void dfs1(int u,int f){
dep[u]=dep[f]+1,siz[u]=1,fa[u]=f;
for(int v:t[u]){
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int topf){
dfn[u]=++idx,top[u]=topf;
if(!son[u]) return;
dfs2(son[u],topf);
for(int v:t[u]){
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
inline void init(){dfs1(1,0),dfs2(1,1);}
}a,b;
void prework(){
bs=sqrt(n*1.0),m=(n+bs-1)/bs;
for(int i=1;i<=m;i++){
st[i]=(i-1)*bs+1,ed[i]=min(n,bs*i);
for(int j=st[i];j<=ed[i];j++) in[j]=i;
}
for(int i=1;i<=n;i++) ltr[i]=in[invp[i]],sum[ltr[i]]+=vis[i];
for(int i=1;i<=m;i++) for(int j=1;j<=m;j++){
int l=st[i],r=ed[i];
for(int k=st[j];k<=ed[j];k++) if(p[k]>=l&&p[k]<=r) cnt[i][j]++;
cnt[i][j]+=cnt[i-1][j];
}
}
void add(int x,int y,int k){
if(in[x]==in[y]){
for(int i=x;i<=y;i++) vis[i]+=k,sum[ltr[i]]+=k;
return;
}
for(int i=x;i<=ed[in[x]];i++) vis[i]+=k,sum[ltr[i]]+=k;
for(int i=st[in[y]];i<=y;i++) vis[i]+=k,sum[ltr[i]]+=k;
for(int i=1;i<=m;i++) sum[i]+=(cnt[in[y]-1][i]-cnt[in[x]][i])*k;
for(int i=in[x]+1;i<in[y];i++) tag[i]+=k;
}
int query(int x,int y){
int res=0;
if(in[x]==in[y]){
for(int i=x;i<=y;i++) res+=vis[p[i]]+tag[in[p[i]]];
return res;
}
for(int i=x;i<=ed[in[x]];i++) res+=vis[p[i]]+tag[in[p[i]]];
for(int i=st[in[y]];i<=y;i++) res+=vis[p[i]]+tag[in[p[i]]];
for(int i=in[x]+1;i<in[y];i++) res+=sum[i];
return res;
}
void solve1(int x,int y,int k){
while(a.top[x]!=a.top[y]){
if(a.dep[a.top[x]]<a.dep[a.top[y]]) swap(x,y);
add(a.dfn[a.top[x]],a.dfn[x],k);
x=a.fa[a.top[x]];
}
if(a.dep[x]>a.dep[y]) swap(x,y);
add(a.dfn[x],a.dfn[y],k);
}
int solve2(int x,int y){
int res=0;
while(b.top[x]!=b.top[y]){
if(b.dep[b.top[x]]<b.dep[b.top[y]]) swap(x,y);
res+=query(b.dfn[b.top[x]],b.dfn[x]);
x=b.fa[b.top[x]];
}
if(b.dep[x]>b.dep[y]) swap(x,y);
res+=query(b.dfn[x],b.dfn[y]);
return res;
}
signed main(){
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>p[i];
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
a.add(u,v);
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
b.add(u,v);
}
a.init(),b.init();
for(int i=1;i<=n;i++) vis[a.dfn[i]]=p[i];
for(int i=1;i<=n;i++) p[b.dfn[i]]=a.dfn[i],invp[a.dfn[i]]=b.dfn[i];
prework();
while(q--){
int x,y,k;
cin>>x>>y>>k;
solve1(x,y,k);
cout<<solve2(x,y)<<"\n";
}
return 0;
}
Comments NOTHING