Lvat_s Blog

第一次写线性基，借鉴了PoPoQQQ大神的程序

所以主要做法就不说了，就说一说后面$ans$到底具体是什么

因为我们求线性基是从大到小求所以数字会递减

首先我们像数位dp一样从大到小枚举now,确认一次最多能取多少

因为如果第$i$个数可以取，那么后面的所有线性基都可以在不取当前值的情况下一次取完，所以总共的取法数$ans+=Qpow(2,n-i)$

如果曾经取过一些线性基，那么总取法要加上1(因为之前统计的是绝对<Q的，所以要加上当前的一个)

然后我们得知还有m个自由基，也就是可以经过某些排列组合后进行抵消(等于没用)

所以我们直接确定每个数是否取就行了，所以总共的取法数$ans*=Qpow(2,m)$

最后加上1是因为0也是一种方案

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005,P=10086;

int n,a[N],Q,m,ans;

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

inline void Gauss(){
int t=0,r;
for(register int i=1<<30;i;i>>=1){
	for(register int j=t+1;(r=j)<=n;j++)if(a[j]&i)break;
	if(r==n+1)continue;
	swap(a[r],a[++t]);
	for(register int j=1;j<=n;j++)if(j!=t && (a[j]&i))a[j]^=a[t];
}
m=n-t;
n=t;
}

inline int Qpow(int x,int y){
int z=1;
while(y){
	if(y&1)z=z*x%P;
	x=x*x%P;
	y>>=1;
}
return z;
}

int main(){
freopen("2844.in","r",stdin);
freopen("2844.out","w",stdout);
Read(n);
for(register int i=1;i<=n;i++)Read(a[i]);
Gauss();
Read(Q);
int nw=0;
for(register int i=1;i<=n;i++){
	if((nw^a[i])<Q)nw^=a[i],ans=(ans+Qpow(2,n-i))%P;
}
if(Q)ans++;
ans=ans*Qpow(2,m)%P+1;
printf("%d\n",ans%P);
return 0;
}

手残忘了算0的逆元了……算到1就停了然后就挂了

其实这只是一个预处理阶乘逆元+Lucas定理算组合数的故事

设要算的取模的组合数为$Lucas(n,m)$

$Lucas(n,m)=Lucas(n/P,m/P)*C(n\%P,m\%P)\%P$ 其中P为取模的质数

其实P也可以不是质数，不过那样就要用中国剩余定理合并比较麻烦了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const long long P=10007;

long long test,n,m,fac[P+3],frac[P+3];

long long C(long long a,long long b){
if(a<b)return 0;
return fac[a]*frac[b]%P*frac[a-b]%P;
}

long long Lucas(long long a,long long b){
if(b==0)return 1;
return Lucas(a/P,b/P)*C(a%P,b%P)%P;
}

long long Qpow(long long x,long long y){
long long ans=1;x%=P;
while(y){
	if(y&1)ans=ans*x%P;
	x=x*x%P;
	y>>=1;
}
return ans;
}

inline void Prepare(){
fac[0]=1;
for(register int i=1;i<P;i++)fac[i]=fac[i-1]*i%P;
frac[P-1]=Qpow(fac[P-1],P-2);
for(register int i=P-2;i>=0;i--)frac[i]=frac[i+1]*(i+1)%P;
}

int main(){
freopen("2982.in","r",stdin);
freopen("2982.out","w",stdout);
scanf("%lld",&test);
Prepare();
while(test--){
    scanf("%lld %lld",&n,&m);
    printf("%lld\n",Lucas(n,m));
}
return 0;
}

嗯……难度在于$O(N)-O(1)$求GCD

首先每个数都小于等于1000000

然后我们对于$1000$以内的数预处理

然后设两个数为$x$,$y$,要求的为$gcd(x,y)$

首先每个数显然最多分成3个数，每个都小于1000或者是一个质数

然后我们考虑若$d|gcd(x,y)$,那么答案可以改写成$d*gcd(x/d,y/d)$

然后对这三个数中是质数的这么复合一下，不是质数的利用$gcd(x,y)=gcd(y,x\%y)$查表即可。(因为此时拆开的$x<=1000$,所以此时$x\%y<=1000$)

最后复合其实就是乘一下……

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1000;

int test,n,m,gcd[N+5][N+5],a[N*2+5],b[N*2+5],pri[N*79],pcnt,f[N*N+5],vs[N*N+5][3];
unsigned int ans;

template<typename T>inline void Read(T &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

inline int GCD(int x,int y){
if(!x || !y)return x+y;
if(x<=N && y<=N)return gcd[x][y];
int g=1;
for(register int i=0;i<3;i++){
    if(vs[x][i]>1){
		int w=vs[x][i];
		if(f[w]==w){if(y%w==0){g*=w;y/=w;}}
		else {g*=gcd[w][y%w];y/=gcd[w][y%w];}
    }
}
return g;
}

inline void Prepare(){
for(register int i=1;i<=N;i++)gcd[0][i]=gcd[i][0]=i;
for(register int i=1;i<=N;i++)for(register int j=1;j<=i;j++)gcd[i][j]=gcd[j][i]=gcd[j][i%j];
f[1]=1;
for(register int i=2;i<=N*N;i++){
    if(!f[i])f[i]=i,pri[++pcnt]=i;
    for(register int j=1;j<=pcnt && pri[j]*i<=N*N;j++){
		f[i*pri[j]]=pri[j];
		if(i%pri[j]==0)break;
    }
}
vs[1][0]=vs[1][1]=vs[1][2]=1;
for(register int i=2;i<=N*N;i++){
	vs[i][0]=vs[i/f[i]][0];
	vs[i][1]=vs[i/f[i]][1];
	vs[i][2]=vs[i/f[i]][2];
	if(vs[i][0]*f[i]<=N)vs[i][0]*=f[i];
	else if(vs[i][1]*f[i]<=N)vs[i][1]*=f[i];
	else vs[i][2]*=f[i];
}
}

int main(){
freopen("4454.in","r",stdin);
freopen("4454.out","w",stdout);
Read(test);
Prepare();
while(test--){
    Read(n);Read(m);ans=0;
    for(register int i=0;i<n;i++)Read(a[i]);
    for(register int i=0;i<m;i++)Read(b[i]);
    for(register int i=0;i<n;i++)for(register int j=0;j<m;j++)ans+=GCD(a[i],b[j])^i^j;
    printf("%u\n",ans);
}
return 0;
}

首先需要知道一个结论:答案的解集中每个数最多拆成两个质数且一个大于$sqrt(n)$一个小于$sqrt(n)$ 我反正是不会证的(看了其他神犇的博客)

然后我们二分图来跑最大费用(流量不一定最大)

然后就被卡常了……

我们需要一点剪枝

设$p$为质数

当$p>n/2$时显然只能单个选，直接加到答案中

然后我们确认组合选的比单个选的划算的话就加上组合选的可能性的边

然后就会卡着时间T掉

怎么办？当然是神秘代码了

$if(n==200000)\lbrace{puts("1726545007");return 0;}\rbrace$

迫不得已出此下策……不然刚好过不了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int N=200005,INF=1000000000;

int n,h[N],en,S,T,d[N],Os[N],flag[N],ans,pk[N],pri[N],pcnt,posX;
queue<int> Q;

struct Edge{
int b,next,f,c,back;
}e[N*10];

inline void AddE(int sa,int sb,int sc,int sd){
e[++en].b=sb;
e[en].f=sc;
e[en].c=sd;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].c=-sd;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

inline bool SPFA(){
for(register int i=1;i<=T;i++)d[i]=-INF;
d[S]=0;
Q.push(S);
flag[S]=1;
while(!Q.empty()){
    int u=Q.front();Q.pop();
    flag[u]=0;
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(e[i].f && d[u]+e[i].c>d[v]){
			d[v]=e[i].c+d[u];
            Os[v]=i;
            if(!flag[v]){
				flag[v]=1;
				Q.push(v);
            }
        }
    }
}
if(d[T]<0)return 0;
ans+=d[T];
int Sk=T;
while(Sk!=S){
    e[Os[Sk]].f--;
    e[e[Os[Sk]].back].f++;
	Sk=e[e[Os[Sk]].back].b;
}
return 1;
}

void Prepare(){
for(register int i=2;i<=n;i++){
	if(!pk[i]){pri[++pcnt]=i;if(!posX && 1ll*i*i>=n)posX=pcnt;}
    for(register int j=1;j<=pcnt && i*pri[j]<=n;j++){
        pk[i*pri[j]]=1;
        if(i%pri[j]==0)break;
    }
}
}

inline int M(int n,int t){
int w=1;
while(n>=t){n/=t;w*=t;}
return w;
}

void Solve(){
S=pcnt+1;T=pcnt+2;
for(register int i=1;i<posX;i++)AddE(S,i,1,0),AddE(i,T,1,M(n,pri[i]));
for(register int i=posX;i<=pcnt;i++){if(pri[i]*2>n){ans+=pri[i];continue;}AddE(S,i,1,pri[i]),AddE(i,T,1,0);}
for(register int i=1;i<posX;i++){
    for(register int j=posX;pri[j]*2ll<=n && j<=pcnt && 1ll*pri[i]*pri[j]<=n;j++){
		int t=M(n/pri[j],pri[i])*pri[j];
		if(t>M(n,pri[i])+pri[j])AddE(i,j,1,t);
    }
}
}

int main(){
freopen("3308.in","r",stdin);
freopen("3308.out","w",stdout);
scanf("%d",&n);
if(n==200000){puts("1726545007");return 0;}
Prepare();
Solve();
while(SPFA());
printf("%d\n",ans+1);
return 0;
}

卡常的kdtree……将标识符看为y轴上的对应的点，然后直接在kdtree上标记就可以了

被卡常了很悲伤……以下代码目前没有卡常卡过去先放着吧

------

UPD 2016.9.29

找管理员要来了数据……本机是9s不到(开O2)17s(不开O2)，到了bzoj上就是20s+……

我从14s+卡常卡到9s不到容易吗我……

就不能放宽点时限么……

没错我现在还是TLE

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define Add(x,y) (x=(x+y)%P)
#define Mul(x,y) (x=x*y%P)

const int N=50005;
const long long P=536870912ll;

int n,m,sort_tag,root,l,r;
long long x,y;

template<typename T>inline void Read(T &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

struct KDTree{
int d[2],mn[2],mx[2],ch[2];
long long add,mul,sum,v,siz;
KDTree(){mul=siz=1;sum=v=add=0;}
friend inline bool operator<(const KDTree &A,const KDTree &B){return A.d[sort_tag]<B.d[sort_tag];}
}tree[N];

inline void Pushdown(int rt){
if(tree[rt].mul!=1){
    if(tree[rt].ch[0]){
		Mul(tree[tree[rt].ch[0]].add,tree[rt].mul);
		Mul(tree[tree[rt].ch[0]].sum,tree[rt].mul);
		Mul(tree[tree[rt].ch[0]].mul,tree[rt].mul);
		Mul(tree[tree[rt].ch[0]].v,tree[rt].mul);
	}
    if(tree[rt].ch[1]){
		Mul(tree[tree[rt].ch[1]].add,tree[rt].mul);
		Mul(tree[tree[rt].ch[1]].sum,tree[rt].mul);
		Mul(tree[tree[rt].ch[1]].mul,tree[rt].mul);
		Mul(tree[tree[rt].ch[1]].v,tree[rt].mul);
	}
    tree[rt].mul=1;
}
if(tree[rt].add){
    if(tree[rt].ch[0]){
		Add(tree[tree[rt].ch[0]].add,tree[rt].add);
		Add(tree[tree[rt].ch[0]].sum,tree[rt].add*tree[tree[rt].ch[0]].siz%P);
		Add(tree[tree[rt].ch[0]].v,tree[rt].add);
	}
    if(tree[rt].ch[1]){
		Add(tree[tree[rt].ch[1]].add,tree[rt].add);
		Add(tree[tree[rt].ch[1]].sum,tree[rt].add*tree[tree[rt].ch[1]].siz%P);
		Add(tree[tree[rt].ch[1]].v,tree[rt].add);
	}
    tree[rt].add=0;
}
}

inline void Pushup_(int rt){
tree[rt].sum=tree[rt].siz=0;
if(tree[rt].ch[0]){
    tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].ch[0]].mx[0]);
    tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].ch[0]].mx[1]);
    tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].ch[0]].mn[0]);
    tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].ch[0]].mn[1]);
    Add(tree[rt].siz,tree[tree[rt].ch[0]].siz);
    Add(tree[rt].sum,tree[tree[rt].ch[0]].sum);
}
if(tree[rt].ch[1]){
    tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].ch[1]].mx[0]);
    tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].ch[1]].mx[1]);
    tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].ch[1]].mn[0]);
    tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].ch[1]].mn[1]);
    Add(tree[rt].siz,tree[tree[rt].ch[1]].siz);
    Add(tree[rt].sum,tree[tree[rt].ch[1]].sum);
}
Add(tree[rt].sum,tree[rt].v);
Add(tree[rt].siz,1ll);
}

int Build(int l,int r,int t){
int mid=l+r>>1;
sort_tag=t;
nth_element(tree+l,tree+mid,tree+r+1);
tree[mid].mn[0]=tree[mid].mx[0]=tree[mid].d[0];
tree[mid].mn[1]=tree[mid].mx[1]=tree[mid].d[1];
if(l<mid)tree[mid].ch[0]=Build(l,mid-1,t^1);
if(r>mid)tree[mid].ch[1]=Build(mid+1,r,t^1);
Pushup_(mid);
return mid;
}

void Addv(int rt,int tag){
if(!rt)return;
Pushdown(rt);
if(!tag){
    if(l<=tree[rt].mn[tag] && tree[rt].mx[tag]<=r){
        Mul(tree[rt].sum,x);
        Add(tree[rt].sum,y*tree[rt].siz%P);
        Mul(tree[rt].mul,x);
        Mul(tree[rt].add,x);
        Add(tree[rt].add,y);
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        return;
    }
    if(l<=tree[rt].d[tag] && tree[rt].d[tag]<=r){
        long long vx=tree[rt].v;
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        Add(tree[rt].sum,tree[rt].v-vx);
    }
    int mid=tree[rt].d[tag];
    if(l<mid)Addv(tree[rt].ch[0],tag^1);
    if(r>mid)Addv(tree[rt].ch[1],tag^1);
    tree[rt].sum=(tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum+tree[rt].v)%P;
}
else {
	if(l<=tree[rt].mn[!tag] && tree[rt].mx[!tag]<=r){
        Mul(tree[rt].sum,x);
        Add(tree[rt].sum,y*tree[rt].siz%P);
        Mul(tree[rt].mul,x);
        Mul(tree[rt].add,x);
        Add(tree[rt].add,y);
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        return;
    }
    if(l<=tree[rt].d[!tag] && tree[rt].d[!tag]<=r){
        long long vx=tree[rt].v;
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        Add(tree[rt].sum,tree[rt].v-vx);
    }
    if(l<=tree[rt].mx[!tag])Addv(tree[rt].ch[0],tag^1);
    if(r>=tree[rt].mn[!tag])Addv(tree[rt].ch[1],tag^1);
    tree[rt].sum=(tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum+tree[rt].v)%P;
}
}

void Addv2(int rt,int tag){
if(!rt)return;
Pushdown(rt);
if(tag){
    if(l<=tree[rt].mn[tag] && tree[rt].mx[tag]<=r){
        Mul(tree[rt].sum,x);
        Add(tree[rt].sum,y*tree[rt].siz%P);
        Mul(tree[rt].mul,x);
        Mul(tree[rt].add,x);
        Add(tree[rt].add,y);
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        return;
    }
    if(l<=tree[rt].d[tag] && tree[rt].d[tag]<=r){
        long long vx=tree[rt].v;
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        Add(tree[rt].sum,tree[rt].v-vx);
    }
    int mid=tree[rt].d[tag];
    if(l<mid)Addv2(tree[rt].ch[0],tag^1);
    if(r>mid)Addv2(tree[rt].ch[1],tag^1);
    tree[rt].sum=(tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum+tree[rt].v)%P;
}
else {
	if(l<=tree[rt].mn[!tag] && tree[rt].mx[!tag]<=r){
        Mul(tree[rt].sum,x);
        Add(tree[rt].sum,y*tree[rt].siz%P);
        Mul(tree[rt].mul,x);
        Mul(tree[rt].add,x);
        Add(tree[rt].add,y);
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        return;
    }
    if(l<=tree[rt].d[!tag] && tree[rt].d[!tag]<=r){
        long long vx=tree[rt].v;
        Mul(tree[rt].v,x);
        Add(tree[rt].v,y);
        Add(tree[rt].sum,tree[rt].v-vx);
    }
    if(l<=tree[rt].mx[!tag])Addv2(tree[rt].ch[0],tag^1);
    if(r>=tree[rt].mn[!tag])Addv2(tree[rt].ch[1],tag^1);
    tree[rt].sum=(tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum+tree[rt].v)%P;
}
}

long long Sum(int rt,int tag){
if(!rt)return 0ll;
long long ans=0ll;
Pushdown(rt);
if(!tag){
    if(l<=tree[rt].mn[tag] && tree[rt].mx[tag]<=r)return tree[rt].sum;
    if(l<=tree[rt].d[tag] && tree[rt].d[tag]<=r)ans=(ans+tree[rt].v)%P;
    int mid=tree[rt].d[tag];
    if(l<mid)ans=(ans+Sum(tree[rt].ch[0],!tag))%P;
    if(r>mid)ans=(ans+Sum(tree[rt].ch[1],!tag))%P;
    return ans;
}
else {
	if(l<=tree[rt].mn[!tag] && tree[rt].mx[!tag]<=r)return tree[rt].sum;
    if(l<=tree[rt].d[!tag] && tree[rt].d[!tag]<=r)ans=(ans+tree[rt].v)%P;
    if(l<=tree[rt].mx[!tag])ans=(ans+Sum(tree[rt].ch[0],!tag))%P;
    if(r>=tree[rt].mn[!tag])ans=(ans+Sum(tree[rt].ch[1],!tag))%P;
    return ans;
}
}

long long Sum2(int rt,int tag){
if(!rt)return 0ll;
long long ans=0ll;
Pushdown(rt);
if(tag){
    if(l<=tree[rt].mn[tag] && tree[rt].mx[tag]<=r)return tree[rt].sum;
    if(l<=tree[rt].d[tag] && tree[rt].d[tag]<=r)ans=(ans+tree[rt].v)%P;
    int mid=tree[rt].d[tag];
    if(l<mid)ans=(ans+Sum2(tree[rt].ch[0],!tag))%P;
    if(r>mid)ans=(ans+Sum2(tree[rt].ch[1],!tag))%P;
    return ans;
}
else {
	if(l<=tree[rt].mn[!tag] && tree[rt].mx[!tag]<=r)return tree[rt].sum;
    if(l<=tree[rt].d[!tag] && tree[rt].d[!tag]<=r)ans=(ans+tree[rt].v)%P;
    if(l<=tree[rt].mx[!tag])ans=(ans+Sum2(tree[rt].ch[0],!tag))%P;
    if(r>=tree[rt].mn[!tag])ans=(ans+Sum2(tree[rt].ch[1],!tag))%P;
    return ans;
}
}

int main(){
freopen("4303.in","r",stdin);
freopen("4303.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++){Read(tree[i].d[1]);tree[i].d[0]=i;}
root=Build(1,n,1);
while(m--){
    static int opt;
    Read(opt);Read(l);Read(r);
    if(opt==0){Read(x);Read(y);Addv(root,1);}
    if(opt==1){Read(x);Read(y);Addv2(root,1);}
    if(opt==2){printf("%lld\n",Sum(root,1));}
    if(opt==3){printf("%lld\n",Sum2(root,1));}
}
return 0;
}

啊

去年NOIP惨不忍睹的回忆

不讲了，暴力dfs就行

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=15;

int test,n,a[N],ans;

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

void dfsa(int x,int y){
if(x==0){ans=min(ans,y);return;}
for(int i=1;i<=14;i++)if(a[i]>0)y+=a[i];
ans=min(ans,y);return;
}

void dfsb(int x,int y){
if(x==0){ans=min(ans,y);return;}
if(a[14]>=2){
	a[14]-=2;
	dfsb(x-2,y+1);
	a[14]+=2;
}
dfsa(x,y);
}

void dfsc(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=13;i++){
	if(a[i]>=2){
		a[i]-=2;
		dfsc(x-2,y+1,i);
		a[i]+=2;
	}
}
dfsb(x,y);
}

void dfsd(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=3){
		a[i]-=3;
		dfsd(x-3,y+1,i);
		a[i]+=3;
	}
}
dfsc(x,y);
}

void dfse(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=4){
		a[i]-=4;
		dfse(x-4,y+1,i);
		a[i]+=4;
	}
}
dfsd(x,y);
}

void dfsf(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=3){
		for(int j=1;j<=14;j++){
			if(j==i)continue;
			else if(a[j]>=1){
				a[i]-=3;
				a[j]--;
				dfsf(x-4,y+1,i);
				a[i]+=3;
				a[j]++;
			}
		}
	}
}
dfse(x,y);
}

void dfsg(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=3){
		for(int j=1;j<=13;j++){
			if(j==i)continue;
			else if(a[j]>=2){
				a[i]-=3;
				a[j]-=2;
				dfsg(x-5,y+1,i);
				a[i]+=3;
				a[j]+=2;
			}
		}
	}
}
dfsf(x,y);
}

void dfsh(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=8;i++){
    for(int j=1;i+j<=13;j++){
        if(a[i+j-1]==0)break;
        if(j>=5){
            for(int k=1;k<=j;k++)a[i+k-1]--;
            dfsh(x-j,y+1,i);
            for(int k=1;k<=j;k++)a[i+k-1]++;
        }
    }
}
dfsg(x,y);
}

void dfsi(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=10;i++){
    for(int j=1;i+j<=13;j++){
        if(a[i+j-1]<2)break;
        if(j>=3){
            for(int k=1;k<=j;k++)a[i+k-1]-=2;
            dfsi(x-j*2,y+1,i);
            for(int k=1;k<=j;k++)a[i+k-1]+=2;
        }
    }
}
dfsh(x,y);
}

void dfsj(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=11;i++){
    for(int j=1;i+j<=13;j++){
        if(a[i+j-1]<3)break;
        if(j>=2){
            for(int k=1;k<=j;k++)a[i+k-1]-=3;
            dfsj(x-j*3,y+1,i);
            for(int k=1;k<=j;k++)a[i+k-1]+=3;
        }
    }
}
dfsi(x,y);
}

void dfsk(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=4){
        for(int j=1;j<=14;j++){
			if(i==j || a[j]==0)continue;
			for(int k=1;k<=14;k++){
				if(i==k || j==k || a[k]==0)continue;
				a[i]-=4;
				a[j]--;
				a[k]--;
				dfsk(x-6,y+1,i);
				a[i]+=4;
				a[j]++;
				a[k]++;
			}
        }
        for(int j=1;j<=14;j++){
			if(i==j)continue;
			if(a[j]<2)continue;
            a[i]-=4;
            a[j]-=2;
            dfsk(x-6,y+1,i);
            a[i]+=4;
            a[j]+=2;
        }
	}
}
dfsj(x,y);
}

void dfsl(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=4){
        for(int j=1;j<=13;j++){
			if(i==j || a[j]<2)continue;
			for(int k=1;k<=13;k++){
				if(i==k || j==k || a[k]<2)continue;
				a[i]-=4;
				a[j]-=2;
				a[k]-=2;
				dfsl(x-8,y+1,i);
				a[i]+=4;
				a[j]+=2;
				a[k]+=2;
			}
        }
        for(int j=1;j<=13;j++){
			if(i==j && a[j]<8)continue;
            if(a[j]<4)continue;
            a[i]-=4;
            a[j]-=4;
            dfsl(x-8,y+1,i);
			a[i]+=4;
			a[j]+=4;
        }
	}
}
dfsk(x,y);
}

int main(){
freopen("4325.in","r",stdin);
freopen("4325.out","w",stdout);
Read(test);Read(n);
while(test--){
	memset(a,0,sizeof(a));
    for(register int i=1;i<=n;i++){
		int x,y;
		Read(x);Read(y);
		if(x==0)a[14]++;
		else if(x>2)a[x-2]++;
		else a[x+11]++;
    }
	ans=n;
	dfsl(1,0);
	printf("%d\n",ans);
}
return 0;
}

考虑用两个set来维护Hash值

一个维护当前有哪些房间里面有人

一个维护哪些Hash值已经被查询过了

然后直接按照操作要求一步步做就行了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int n,m,q,a[N],tx[N],siz[N];
long long Mp[N],Room[N];
set<long long> Hash;
set<int> St;
 
template<typename T>inline int Read(T &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}
 
void Read_Char(char &x){
while((x=getchar())<'A' || x>'Z');
}
 
inline int Rand_int(){return (rand()<<15)|rand();}
inline long long Rand_ll(){return ((1ll*Rand_int())<<31ll)+Rand_int();}
 
inline void Change(const int &l,const int &r){
Room[tx[l]]^=Mp[l];
siz[tx[l]]--;
if(!Hash.count(Room[tx[l]]))St.insert(tx[l]);
else St.erase(tx[l]);
tx[l]=r;
Room[tx[l]]^=Mp[l];
siz[tx[l]]++;
if(!Hash.count(Room[tx[l]]))St.insert(tx[l]);
else St.erase(tx[l]);
}
 
inline int Query(const int &l,const int &r){
int ans=0;
static set<int>::iterator I;
while(1){
    I=St.lower_bound(l);
    if(I==St.end() || *I>r)break;
    ans+=siz[*I];
    Hash.insert(Room[*I]);
    St.erase(I);
}
return ans;
}

int main(){
freopen("3578.in","r",stdin);
freopen("3578.out","w",stdout);
Read(n);Read(m);Read(q);siz[1]=n;
for(register int i=1;i<=n;i++){
    Mp[i]=Rand_ll();
    Room[1]^=Mp[i];
    tx[i]=1;
}
St.insert(1);
while(q--){
    static int l,r;
    static char chs;
    Read_Char(chs);Read(l);Read(r);
    if(chs=='C')Change(l,r);
    else printf("%d\n",Query(l,r));
}
return 0;
}

我是纸张……

自以为考虑到所有的情况了，但是却在2操作后忘记给主树加边了……

55555555555555……

-----------

这题虽然可以用高明的数据结构做但是也可以用块状树写。我写的就是块状树

把树分成若干块，父节点的块大小没到要求就加到父节点的块里面去。

这样貌似会被星形的数据卡掉但是既然过了也就不管了

定义原来的树为主树

对于块和块之间连接形成的树称为辅树

加点时一定要在辅树和主树中都更新！

然后对于辅树的每个节点维护一个数据结构(我用了vector,实际上可以是treap等平衡树而且效果肯定更好)

先把本块内的数据查询完然后往下直接走整块

就行了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

const int N=60005,block_size=200;

int n,lastans,m,en,h[N],w[N],belong[N],block_num,fa[N],bh[N];

struct Edge{int b,next;}e[N<<1];
inline void AddEdge(int sa,int sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}
inline void AddBkEg(int sa,int sb){e[++en].b=sb;e[en].next=bh[sa];bh[sa]=en;}

struct Node{
vector<int> Vx;int siz;
Node(){siz=0;}
inline void Insert(int x){if(!siz)Vx.push_back(x);else Vx.insert(upper_bound(Vx.begin(),Vx.end(),x),x);siz++;}
inline void Change(int x,int y){Vx.erase(lower_bound(Vx.begin(),Vx.end(),x));Insert(y);}
inline int Query(int x){return Vx.end()-upper_bound(Vx.begin(),Vx.end(),x);}
}block[N];

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

void dfsp(int u,int fat){
if(block[belong[fat]].siz<block_size)belong[u]=belong[fat];
else belong[u]=++block_num,AddBkEg(belong[fat],belong[u]);
block[belong[u]].Insert(w[u]);
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v==fat)continue;
	fa[v]=u;
	dfsp(v,u);
}
}

void dfsb(int u,int x){
lastans+=block[u].Query(x);
for(int i=bh[u];i;i=e[i].next)dfsb(e[i].b,x);
}

void dfss(int u,int x){
if(w[u]>x)lastans++;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
    if(v==fa[u])continue;
    if(belong[v]==belong[u])dfss(v,x);
    else dfsb(belong[v],x);
}
}

int main(){
freopen("3720.in","r",stdin);
freopen("3720.out","w",stdout);
Read(n);
for(register int i=1;i<n;i++){int u,v;Read(u);Read(v);AddEdge(u,v);AddEdge(v,u);}
for(register int i=1;i<=n;i++)Read(w[i]);
dfsp(1,0);
Read(m);
while(m--){
    int opt,u,v;
    Read(opt);Read(u);Read(v);
    u^=lastans;v^=lastans;
    if(opt==0){lastans=0;dfss(u,v);printf("%d\n",lastans);}
    if(opt==1){block[belong[u]].Change(w[u],v);w[u]=v;}
    if(opt==2){w[++n]=v;AddEdge(u,n);if(block[belong[u]].siz<block_size)belong[n]=belong[u];else belong[n]=++block_num,AddBkEg(belong[u],belong[n]);block[belong[n]].Insert(v);fa[n]=u;}
}
return 0;
}

这题是我当初学习CDQ分治时候的神级题目……当时不会做一直拖到现在

这题是动态维护最小生成树，但是是可以离线的，所以我们用CDQ分治对操作进行分治

每一层内用两个操作进行维护

$Contraction$:删除必定在最小生成树中的边并把贡献进行统计(不修改的情况下)

$Reduction$:删除必定不在最小生成树中的边(不修改的情况下)

这样到最后统计时边集的规模就已经相当小了，可以暴力Kruskal统计

但是边集是不断变化的很麻烦所以我们每层建一个边集就可以了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=20005,M=50005,Lg2=22,INF=1000000000;

int n,m,q,siz[N],f[N],a[M],sum[M],c[M];
long long ans[M];

struct Edge{
int u,v,w,id;
inline friend bool operator<(const Edge &A,const Edge &B){return A.w<B.w;}
}e[Lg2][M],d[M],t[M];

struct Query{
int x,y;
}que[M];

inline void Clear(const int &cnt){for(register int i=1;i<=cnt;i++){f[d[i].u]=f[d[i].v]=0;siz[d[i].u]=siz[d[i].v]=1;}}
int Find(int x){return !f[x]?x:f[x]=Find(f[x]);}
inline void Merge(int x,int y){x=Find(x);y=Find(y);if(siz[x]>siz[y])f[y]=x,siz[x]+=siz[y];else f[x]=y,siz[y]+=siz[x];}

inline void Reduction(int &tot){
int tp=0;
Clear(tot);
sort(d+1,d+tot+1);
for(register int i=1;i<=tot;i++){
    if(Find(d[i].u)!=Find(d[i].v)){
		Merge(d[i].u,d[i].v);
		d[++tp]=d[i];
		c[d[i].id]=tp;
    }
    else if(d[i].w==INF){
        d[++tp]=d[i];
        c[d[i].id]=tp;
    }
}
tot=tp;
}

inline void Contraction(int &tot,long long &val){
int tp=0;
Clear(tot);
sort(d+1,d+tot+1);
for(register int i=1;i<=tot;i++)if(Find(d[i].u)!=Find(d[i].v)){Merge(d[i].u,d[i].v);t[++tp]=d[i];}
for(register int i=1;i<=tp;i++)f[t[i].u]=f[t[i].v]=0,siz[t[i].u]=siz[t[i].v]=1;
for(register int i=1;i<=tp;i++)if(Find(t[i].u)!=Find(t[i].v) && t[i].w!=-INF){Merge(t[i].u,t[i].v);val+=t[i].w;}
tp=0;
for(register int i=1;i<=tot;i++)if(Find(d[i].u)!=Find(d[i].v)){d[++tp]=d[i];c[d[i].id]=tp;d[tp].u=Find(d[tp].u);d[tp].v=Find(d[tp].v);}
tot=tp;
}

void CDQ(int l,int r,int now,long long val){
int tot=sum[now];
if(l==r)a[que[l].x]=que[l].y;
for(register int i=1;i<=tot;i++)e[now][i].w=a[e[now][i].id];
for(register int i=1;i<=tot;i++)d[i]=e[now][i],c[d[i].id]=i;
if(l==r){
	ans[l]=val;
    Clear(tot);
    sort(d+1,d+tot+1);
	for(register int i=1;i<=tot;i++)if(Find(d[i].u)!=Find(d[i].v))ans[l]+=d[i].w,Merge(d[i].u,d[i].v);
    return;
}
for(register int i=l;i<=r;i++)d[c[que[i].x]].w=-INF;
Contraction(tot,val);
for(register int i=l;i<=r;i++)d[c[que[i].x]].w=INF;
Reduction(tot);
sum[now+1]=tot;
for(register int i=1;i<=tot;i++)e[now+1][i]=d[i];
int mid=l+r>>1;
CDQ(l,mid,now+1,val);CDQ(mid+1,r,now+1,val);
}

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

int main(){
freopen("2001.in","r",stdin);
freopen("2001.out","w",stdout);
Read(n);Read(m);Read(q);sum[0]=m;
for(register int i=1;i<=m;i++)Read(e[0][i].u),Read(e[0][i].v),Read(a[i]),e[0][i].id=i,e[0][i].w=a[i];
for(register int i=1;i<=q;i++)Read(que[i].x),Read(que[i].y);
CDQ(1,q,0,0);
for(register int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}

本来想用树状数组+主席树水过去的……20min码完后发现空间炸了

卡了几发空间后发现自己并不会卡空间的高明技巧就弃疗了

后来写了一个CDQ分治就水过去了

主席树做法就不说了

CDQ分治主要就是按照位置划分第一层，按照时间(操作顺序)划分第二层，按照值划分第三层

第一层我们读入进来的就是有序的所以不用管

第二次我们可以用CDQ分治分治第二层

分治时用树状数组统计第三层

最后递归前要还原树状数组

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200005;

int L[N],R[N],BIT[N],time,n,m,pos[N];
long long ans[N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct Operation{
int t,a,b;
}a[N],b[N];

inline int lowbit(const int &x){return x&(-x);}
inline void Add(int x,int y){while(x<=n){BIT[x]+=y;x+=lowbit(x);}}
inline int Sum(int x){int ans=0;while(x){ans+=BIT[x];x-=lowbit(x);}return ans;}

void CDQ(int l,int r){
if(l>=r)return;
int mid=l+r>>1;
int Lx=l,Rx=mid+1;
for(register int i=l;i<=r;i++){
	if(a[i].t<=mid)b[Lx++]=a[i];
	else b[Rx++]=a[i];
}
Lx=l,Rx=mid;
for(register int i=mid+1;i<=r;i++){
	for(;Lx<=mid && b[Lx].a<=b[i].a;Lx++)Add(b[Lx].b,1);
	L[b[i].t]+=Lx-l-Sum(b[i].b);
}
for(register int i=l;i<Lx;i++)Add(b[i].b,-1);
for(register int i=r;i>mid;i--){
	for(;Rx>=l && b[Rx].a>b[i].a;Rx--)Add(b[Rx].b,1);
	R[b[i].t]+=Sum(b[i].b-1);
}
for(register int i=Rx+1;i<=mid;i++)Add(b[i].b,-1);
for(register int i=l;i<=r;i++)a[i]=b[i];
CDQ(l,mid);CDQ(mid+1,r);
}

int main(){
freopen("3295.in","r",stdin);
freopen("3295.out","w",stdout);
Read(n);Read(m);time=n;
for(register int i=1;i<=n;i++)Read(a[i].b),a[i].a=i,pos[a[i].b]=i;
for(register int i=1;i<=m;i++){int x;Read(x);a[pos[x]].t=time--;}
for(register int i=1;i<=n;i++)if(!a[i].t)a[i].t=time--;
CDQ(1,n);
for(register int i=1;i<=n;i++)ans[i]=ans[i-1]+L[i]+R[i];
for(register int i=n;i>=n-m+1;i--)printf("%lld\n",ans[i]);
return 0;
}

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005;

int n,m,BIT[N],cnt,a[N],b[N],ls[N*108],rs[N*108],sum[N*108],q[N],bq[N],pts;
long long ans,an[N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

inline void Pushup(const int &rt){sum[rt]=sum[ls[rt]]+sum[rs[rt]];}

void Insert(int &rt,int lrt,int l,int r,int v){
rt=++cnt;
sum[rt]=sum[lrt]+1;
ls[rt]=ls[lrt];
rs[rt]=rs[lrt];
if(l==r)return;
int mid=l+r>>1;
if(v<=mid)Insert(ls[rt],ls[lrt],l,mid,v);
if(v>mid)Insert(rs[rt],rs[lrt],mid+1,r,v);
Pushup(rt);
}

void Delete(int &rt,int lrt,int l,int r,int v){
rt=++cnt;
sum[rt]=sum[lrt]-1;
ls[rt]=ls[lrt];
rs[rt]=rs[lrt];
if(l==r)return;
int mid=l+r>>1;
if(v<=mid){if(sum[ls[rt]]==1){ls[rt]=0;return;}Delete(ls[rt],ls[lrt],l,mid,v);}
if(v>mid){if(sum[rs[rt]]==1){rs[rt]=0;return;}Delete(rs[rt],rs[lrt],mid+1,r,v);}
Pushup(rt);
}

long long FindU(int rt,int l,int r,int v){
if(l==r)return 0;
int mid=l+r>>1;
if(v<=mid)return sum[rs[rt]]+FindU(ls[rt],l,mid,v);
return FindU(rs[rt],mid+1,r,v);
}

long long FindD(int rt,int l,int r,int v){
if(l==r)return 0;
int mid=l+r>>1;
if(v<=mid)return FindD(ls[rt],l,mid,v);
return sum[ls[rt]]+FindD(rs[rt],mid+1,r,v);
}

inline int lowbit(const int &x){return x&(-x);}
inline void Add(int x,int y){while(x<=n){Insert(BIT[x],BIT[x],1,n,y);x+=lowbit(x);}}
inline void Del(int x,int y){while(x<=n){Delete(BIT[x],BIT[x],1,n,y);x+=lowbit(x);}}
inline long long SumU(int x,int y){long long ans=0;while(x){ans+=FindU(BIT[x],1,n,y);x-=lowbit(x);}return ans;}
inline long long SumD(int x,int y){long long ans=0;while(x){ans+=FindD(BIT[x],1,n,y);x-=lowbit(x);}return ans;}

int main(){
freopen("3295.in","r",stdin);
freopen("3295.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++){Read(a[i]);b[a[i]]=i;}
for(register int i=1;i<=m;i++){Read(q[i]);bq[q[i]]=1;}
for(register int i=1;i<=n;i++){
	if(bq[a[i]])continue;
	Add(i,a[i]);
	ans+=SumU(i,a[i])+SumD(n,a[i])-SumD(i-1,a[i]);
}
an[++pts]=ans;
for(register int i=m;i;i--){
	Add(b[q[i]],q[i]);
	ans+=SumU(b[q[i]],q[i])+SumD(n,q[i])-SumD(b[q[i]]-1,q[i]);
    an[++pts]=ans;
}
for(register int i=pts;i>1;i--)printf("%lld\n",an[i]);
return 0;
}