狗都不用（？）的二叉/分治模板
_13858886080 · · 个人记录
二分查找（自己背住却仍记了模板）
#include<bits/stdc++.h>
using namespace std;
int a,s[100],d;
int efcz(int q,int w,int e){
int m=(q+w)/2;
while(!(s[m]==e&&s[m-1]!=e)){
if(s[m]>=e)w=m-1;
else q=m+1;
m=(q+w)/2;
}
return m;
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>a;
for(int i=1;i<=a;i++)cin>>s[i];
cin>>d;
cout<<efcz(1,a,d);
return 0;
}超精简的快速幂（看不懂……）
#include<bits/stdc++.h>
using namespace std;
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
unsigned long long a,b,c,t=1;
scanf("%lld%lld",&a,&b);
for(c=a;b;c*=c,b/=2)if(b%2)t*=c;
printf("%lld\n",t);
return 0;
}手写sort（STL不香吗……）
#include<bits/stdc++.h>
using namespace std;
int a,s[100001];
void ssort(int l,int r){
if(l>=r)return;
int i=l,j=r;
while(j!=i){
while(j>i&&s[j]>s[i])j--;
if(j!=i)swap(s[i],s[j]);
else break;
while(j>i&&s[j]>s[i])i++;
if(j!=i)swap(s[i],s[j]);
}
ssort(l,i-1);
ssort(i+1,r);
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>a;
for(int i=1;i<=a;i++)cin>>s[i];
ssort(1,a);
for(int i=1;i<=a;i++)cout<<s[i]<<" ";
return 0;
}逆序对之归并排序（无聊时可以用来卡常）
#include<bits/stdc++.h>
using namespace std;
int n,a[100005],r[100005],d;
void nsd(int s,int t) {
if(s==t) return;
int mid=(s+t)/2;
nsd(s,mid);
nsd(mid+1,t);
int i=s,j=mid+1,k=s;
while(i<=mid && j<=t) {
if(a[i]<a[j]) {
r[k]=a[i];
k++;
i++;
}
else {
r[k]=a[j];
k++;
j++;
d+=mid-i+1;
}
}
while(i<=mid) {
r[k]=a[i];
k++;
i++;
}
while(j<=t) {
r[k]=a[j];
k++;
j++;
}
for(int i=s; i<=t; i++)a[i]=r[i];
}
int main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; i++)scanf("%d",&a[i]);
nsd(1,n);
for(int i=1; i<=n; i++)printf("%d ",a[i]);
cout<<d;
return 0;
}堆排序（脑子有坑才用这玩意）
#include<bits/stdc++.h>
using namespace std;
int a,s[10001],sk;
void gx(int k){
sk++;
s[sk]=k;
int x=sk;
while(x!=1){
if(s[x/2]>s[x]){
swap(s[x/2],s[x]);
x/=2;
}
else return ;
}
return;
}
void ggx(){
sk--;
swap(s[1],s[sk+1]);
s[sk+1]=0;
int x=1;
while(x<=sk){
if(x*2+1<=sk){
if(s[x*2]<s[x*2+1]){
if(s[x]>s[x*2]){
swap(s[x*2],s[x]);
x*=2;
}
else return;
}
else {
if(s[x]>s[x*2+1]){
swap(s[x*2+1],s[x]);
x=x*2+1;
}
else return;
}
}
else if(x*2<=sk&&s[x*2]<s[x]){
swap(s[x*2],s[x]);
x*=2;
}
else return ;
}
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>a;
for(int i=1;i<=a;i++){
int x;
cin>>x;
gx(x);
}
for(int i=1;i<=a;i++){
cout<<s[1]<<" ";
ggx();
}
return 0;
}P3390矩阵快速幂
#include<bits/stdc++.h>
using namespace std;
inline long long read(){
long long p=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
return f*p;
}
struct data{
int q,w;long long e[101][101];
inline data operator*(const data &m)const{
data x;
x.q=q;x.w=m.w;
for(int i=1;i<=x.q;i++)
for(int j=1;j<=x.w;j++){
x.e[i][j]=0;
for(int k=1;k<=w;k++)
x.e[i][j]=(x.e[i][j]+e[i][k]*m.e[k][j])%1000000007;
}
return x;
}
}kkl,llk;
int a;
long long s;
int main(){
a=read();s=read()-1;
kkl.q=kkl.w=llk.q=llk.w=a;
for(int i=1;i<=a;i++)for(int j=1;j<=a;j++)
kkl.e[i][j]=llk.e[i][j]=read();
while(s>0){
if(s%2==1)llk=kkl*llk;
s/=2;kkl=kkl*kkl;
}
for(int i=1;i<=a;i++){
for(int j=1;j<=a;j++)printf("%lld ",llk.e[i][j]);
printf("\n");
}
return 0;
}P3806点分治（一个非常不板子到必须另外加个板子的板子）
#include<bits/stdc++.h>
/*
给定一棵有n个点的树,询问树上距离为k的点对是否存在
*/
using namespace std;
inline int read(){
int p=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
return f*p;
}
int a,s,gen,shudaxiao,ans[400001],sna[400001];
int fir[200001],nex[400001],son[400001],len[400001],tot;
void add(int x,int y,int z){len[++tot]=z;son[tot]=y;nex[tot]=fir[x];fir[x]=tot;}
int daxiao[200001],ma[200001];
bool vis[200001];
inline void chushihua(int z){ma[gen=0]=a;shudaxiao=z;}
inline void zhaogen(int z,int x){
daxiao[z]=1;ma[z]=0;
for(int i=fir[z];i;i=nex[i])if(son[i]!=x&&!vis[son[i]])
zhaogen(son[i],z),daxiao[z]+=daxiao[son[i]],ma[z]=max(ma[z],daxiao[son[i]]);
ma[z]=max(ma[z],shudaxiao-daxiao[z]);if(ma[gen]>ma[z])gen=z;
}
int chang[400001],tt,dian[400001];
bool kkl[120000001];
int mtf[400001];
inline void zhaochang(int z,int x){
chang[++tt]=dian[z];
for(int i=fir[z];i;i=nex[i])if(son[i]!=x&&!vis[son[i]])
dian[son[i]]=dian[z]+len[i],zhaochang(son[i],z);
}
inline void qiuans(int z){
int p=0;
for(int i=fir[z];i;i=nex[i])if(!vis[son[i]]){
dian[son[i]]=len[i];tt=0;zhaochang(son[i],z);
for(int j=1;j<=tt;j++)for(int k=1;k<=s;k++)
if(sna[k]>=chang[j]&&kkl[sna[k]-chang[j]])ans[k]=true;
for(int j=1;j<=tt;j++)mtf[++p]=chang[j],kkl[chang[j]]=true;
}
for(int i=1;i<=p;i++)kkl[mtf[i]]=false;
}
inline void fenzhi(int z){
vis[z]=kkl[0]=true;qiuans(z);
for(int i=fir[z];i;i=nex[i])if(!vis[son[i]]){
chushihua(daxiao[son[i]]);
zhaogen(son[i],z);fenzhi(gen);
}
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
a=read();s=read();
for(int i=1,z,x,c;i<a;++i){z=read(),x=read(),c=read();add(z,x,c);add(x,z,c);}
for(int i=1;i<=s;++i)sna[i]=read();
chushihua(a);zhaogen(1,0);fenzhi(gen);
for(int i=1;i<=s;++i){if(ans[i])printf("AYE\n");else printf("NAY\n");}
return 0;
}P2634聪聪可可（点分治的另一个板子）
#include<bits/stdc++.h>
/*
在纸上画n个点,并用n-1条边把这n个点恰好连通(其实这就是一棵树),并且每条边上都有一个数
接下来由聪聪和可可分别随即选一个点(当然他们选点时是看不到这棵树的),
如果两个点之间所有边上数的和加起来恰好是3的倍数,则判聪聪赢,否则可可赢
聪聪非常爱思考问题,在每次游戏后都会仔细研究这棵树,希望知道对于这张图自己的获胜概率是多少
以即约分数形式输出这个概率(即a/b的形式,其中a和b必须互质,如果概率为1,输出1/1)
*/
using namespace std;
inline int read(){
int p=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
return f*p;
}
int a,gen,shudaxiao,ans;
int fir[200001],nex[400001],son[400001],len[400001],tot;
void add(int x,int y,int z){len[++tot]=z;son[tot]=y;nex[tot]=fir[x];fir[x]=tot;}
int daxiao[200001],ma[200001];
bool vis[200001];
inline void chushihua(int z){ma[gen=0]=a;shudaxiao=z;}
inline void zhaogen(int z,int x){
daxiao[z]=1;ma[z]=0;
for(int i=fir[z];i;i=nex[i])if(son[i]!=x&&!vis[son[i]])
zhaogen(son[i],z),daxiao[z]+=daxiao[son[i]],ma[z]=max(ma[z],daxiao[son[i]]);
ma[z]=max(ma[z],shudaxiao-daxiao[z]);if(ma[gen]>ma[z])gen=z;
}
int chang[3],tt,dian[400001];
inline void zhaochang(int z,int x){
++chang[dian[z]];
for(int i=fir[z];i;i=nex[i])if(son[i]!=x&&!vis[son[i]])
dian[son[i]]=(dian[z]+len[i])%3,zhaochang(son[i],z);
}
inline int qiuans(int z,int x){
chang[0]=chang[1]=chang[2]=0;dian[z]=x%3;
zhaochang(z,0);
return chang[0]*chang[0]+chang[1]*chang[2]+chang[2]*chang[1];
}
inline void fenzhi(int z){
vis[z]=true;ans+=qiuans(z,0);
for(int i=fir[z];i;i=nex[i])if(!vis[son[i]]){
ans-=qiuans(son[i],len[i]);chushihua(daxiao[son[i]]);
zhaogen(son[i],z);fenzhi(gen);
}
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>a;
for(int i=1;i<a;i++){int z=read(),x=read(),c=read()%3;add(z,x,c);add(x,z,c);}
chushihua(a);zhaogen(1,0);fenzhi(gen);
int z=__gcd(ans,a*a);
printf("%d/%d",ans/z,a*a/z);
return 0;
}P6329点分树（来自地底的不可名状产物）
#include<bits/stdc++.h>
/*
在一片土地上有n个城市,通过n-1条无向边互相连接,形成一棵树的结构,相邻两个城市的距离为1,其中第i个城市的价值为value_i
不幸的是,这片土地常常发生地震,并且随着时代的发展,城市的价值也往往会发生变动
接下来你需要在线处理m次操作:
0 x k表示发生了一次地震,震中城市为x,影响范围为k,所有与x距离不超过k的城市都将受到影响,该次地震造成的经济损失为所有受影响城市的价值和。
1 x y表示第x个城市的价值变成了y
为了体现程序的在线性,操作中的x,y,k都需要异或你程序上一次的输出来解密,如果之前没有输出,则默认上一次的输出为0
*/
using namespace std;
inline int read(){
int p=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
return f*p;
}
int a,s,d[200005],shudaxiao,lla,shen1,shen2,gen,genn,tt;
int fir[200005],nex[200005],son[200005],tot;
inline void add(int z,int x){son[++tot]=x;nex[tot]=fir[z];fir[z]=tot;}
int daxiao[200005],ma[200005];
bool vis[200005];
struct data{int q,w,e;};vector<data>ans[200005];
struct xianduanshu{
vector<int>shu;
int dcss(int z){return (-z)&z;}
void jia(int z,int x){z++;while(z<shu.size()){shu[z]+=x;z+=dcss(z);}}
int ca(int z){int re=0;z=min(z+1,int(shu.size()-1));while(z>0){re+=shu[z];z-=dcss(z);}return re;}
}tr[200005][2];
inline void chushihua(int z){ma[gen=0]=a;shudaxiao=z;}
inline void zhaogen(int z,int x){
daxiao[z]=1;ma[z]=0;
for(int i=fir[z];i;i=nex[i])if(son[i]!=x&&!vis[son[i]])
zhaogen(son[i],z),daxiao[z]+=daxiao[son[i]],ma[z]=max(ma[z],daxiao[son[i]]);
ma[z]=max(ma[z],shudaxiao-daxiao[z]);if(ma[gen]>ma[z])gen=z;
}
void zhaoshen(int z,int x,int c){
shen2=max(shen2,c);ans[z].push_back(data{genn,tt,c});
for(int i=fir[z];i;i=nex[i])if(!vis[son[i]]&&son[i]!=x)zhaoshen(son[i],z,c+1);
}
void fenshu(int z){
ans[z].push_back(data{z,0,0});shen1=0;genn=z;
for(int i=fir[z];i;i=nex[i])if(!vis[son[i]]){
shen2=0;tt++;zhaoshen(son[i],z,1);
shen1=max(shen1,shen2);
tr[tt][1].shu.resize(shen2+2);
}
tr[z][0].shu.resize(shen1+2);vis[z]=true;
for(int i=fir[z];i;i=nex[i])if(!vis[son[i]])
chushihua(daxiao[son[i]]),zhaogen(son[i],0),fenshu(gen);
}
void bian(int z,int x){
for(int i=0;i<ans[z].size();i++){
tr[ans[z][i].q][0].jia(ans[z][i].e,x);
if(ans[z][i].w)tr[ans[z][i].w][1].jia(ans[z][i].e,x);
}
}
int qiu(int z,int x){
int re=0;
for(int i=0;i<ans[z].size();i++)if(x-ans[z][i].e>=0)
re+=tr[ans[z][i].q][0].ca(x-ans[z][i].e)-tr[ans[z][i].w][1].ca(x-ans[z][i].e);
return re;
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
a=read();s=read();
for(int i=1;i<=a;i++)d[i]=read();
for(int i=1;i<a;i++){int z=read(),x=read();add(z,x);add(x,z);}
chushihua(a);zhaogen(1,0);fenshu(gen);
cout<<shen1<<" "<<shen2<<" "<<gen<<" "<<genn<<" "<<tt<<" "<<shudaxiao<<endl;
for(int i=1;i<=a;i++)bian(i,d[i]);
for(int i=1;i<=s;i++){
int z=read(),x=read()^lla,c=read()^lla;
if(z==1)bian(x,c-d[x]),d[x]=c;
else printf("%d\n",lla=qiu(x,c));
}
return 0;
}P3810CDQ 分治三维偏序（啊吧啊吧）
#include<bits/stdc++.h>
/*
有n个元素,第i个元素有a_i,b_i,c_i三个属性,
设f(i)表示满足a_j<a_i且b_j<b_i且c_j<c_i且j!=i的j的数量
对于d∈[0,n),求f(i)=d的数量
*/
using namespace std;
inline int read(){
int p=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
return f*p;
}
int a,s,d,tt,ans[2000005];
struct data{
int q,w,e,r,t;
}f[2000005],g[2000005],h[2000005];
bool scp(data z,data x){return z.q<x.q||z.q==x.q&&(z.w<x.w||z.w==x.w&&z.e<x.e);}
bool goc(data z,data x){return z.w<x.w||z.w==x.w&&z.e<x.e;}
int p[2000005];
int lb(int z){return (-z)&z;}
void shangchuan(int z,int x){while(z<=s){p[z]+=x;z+=lb(z);}}
int xunwen(int z){int re=0;while(z){re+=p[z];z-=lb(z);}return re;}
void qiuqiu(int z,int x){
if(z==x)return ;
int mid=(z+x)/2;
qiuqiu(z,mid);qiuqiu(mid+1,x);int p=z;
sort(g+z,g+mid+1,goc);sort(g+mid+1,g+x+1,goc);
for(int i=mid+1;i<=x;i++){
while(g[i].w>=g[p].w&&p<=mid){shangchuan(g[p].e,g[p].t);p++;}
g[i].r+=xunwen(g[i].e);
}
for(int i=z;i<p;i++)shangchuan(g[i].e,-g[i].t);
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
a=read();s=read();
for(int i=1;i<=a;i++)f[i].q=read(),f[i].w=read(),f[i].e=read();
sort(f+1,f+a+1,scp);
for(int i=1;i<=a;i++){
tt++;
if(f[i].q!=f[i+1].q||f[i].w!=f[i+1].w||f[i].e!=f[i+1].e){g[++d]=f[i];g[d].t=tt;tt=0;}
}
qiuqiu(1,d);
for(int i=1;i<=d;i++)ans[g[i].r+g[i].t]+=g[i].t;
for(int i=1;i<=a;i++)printf("%d\n",ans[i]);
return 0;
}