4
11
2016
0

[BZOJ4407] 于神之怒加强版

一道反演的好题

首先我们需要推一下式子(写在纸上发现不太好写在电脑上)

拍照太烦了……其实就是Claris博客上的公式

然后倒数第二行那个式子的前缀和我不太会。。本来想问Claris的后来自己推了一下就会了

网上题解都好玄学啊

首先对于这么一个式子(用画图画的请见谅……我不会LateX)

我们把这个式子的值用一个函数F(D)表示

然后我们可以发现:对于D为质数,那么d只有两个值:一个是1,一个是D

那么我们可以暴力快速幂乘起来就可以了

如果D不是质数,为了简化我们假设这个D可以由两个质数相乘

那么d的取值可以是:1,第一个质数,第二个质数,两个质数之积

那么我们设f[i]=i是质数则为ik,否则为0

g[i]=这个和数会由哪些质数组成

我们就可得到F[i*pri[j]]=F[pri[j]]*F[i],因为这个F[i*pri[j]]会由F[i]和F[i*pri[j]]组成,那么两个sigma相乘自然就是这个值了

对于两个质数以上的乘积我觉得和上面一样的。。主要分g[i]是否等于i(i是质数)和g[i]不等于i两种情况考虑,就可以了

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

const int N=5000000,Mod=1000000007;

int T,n,m,k,pri[N/5+1],mu[N+5],tab[N+5],g[N+5],sum[N+5],F[N+5],f[N+5],cnt;

int Pow(int x,int y){
int base=x,ans=1;
while(y){
	if(y&1)ans=1ll*ans*base%Mod;
	base=1ll*base*base%Mod;
	y>>=1;
}
return ans;
}

void Prepare(){
mu[1]=1;
F[1]=1;
for(int i=2;i<=N;i++){
	if(!tab[i]){pri[++cnt]=i;mu[i]=-1;f[i]=Pow(i,k);F[i]=f[i]-1;g[i]=i;}
	for(int j=1;j<=cnt && i*pri[j]<=N;j++){
		tab[pri[j]*i]=1;
		if(i%pri[j]){
			mu[i*pri[j]]=-mu[i];
			g[i*pri[j]]=pri[j];
			F[i*pri[j]]=1ll*F[pri[j]]*F[i]%Mod;
		}
		else{
			mu[i*pri[j]]=0;
			g[i*pri[j]]=g[i]*pri[j];
            F[i*pri[j]]=g[i]!=i?1ll*F[i/g[i]]*F[g[i]*pri[j]]%Mod:1ll*F[i]*f[pri[j]]%Mod;
			break;
		}
	}
}
for(int i=2;i<=N;i++)F[i]=(F[i-1]+F[i])%Mod;
}

int Solve(){
int ans=0,j;
for(int i=1;i<=n && i<=m;i=j+1){
	j=min(n/(n/i),m/(m/i));
    ans=(ans+1ll*(F[j]-F[i-1]+Mod)*(n/i)%Mod*(m/i)%Mod)%Mod;
}
return ans;
}

int main(){
freopen("4407.in","r",stdin);
freopen("4407.out","w",stdout);
scanf("%d %d",&T,&k);
Prepare();
while(T--){
	scanf("%d %d",&n,&m);
    printf("%d\n",Solve());
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
10
2016
0

[BZOJ2809] [Apio2012]dispatching

首先我们确定了领导者和派遣出去的忍着数目就确定了答案

那么我们枚举领导者,每次一定派遣薪水最少的忍者们

然后先DFS,然后每次超过m我们就在可并堆中pop掉薪水最多的忍着

因为薪水是正数,所以这样做是对的

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

int n,h[100005],en,siz[100005],root[100005],cnt;
long long m,ans,sum[100005];

struct Ninja{
int b;
long long c,l;
}ninja[100005];

struct Edge{
int b,next;
}e[1000005];

struct Heap{
int l,r,dis;
long long v;
}heap[100005];

void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

int Newheap(long long x){
heap[++cnt].v=x;
heap[cnt].l=heap[cnt].r=heap[cnt].dis=0;
return cnt;
}

int Merge(int A,int B){
if(!A)return B;
if(!B)return A;
if(heap[A].v<heap[B].v)swap(A,B);
heap[A].r=Merge(heap[A].r,B);
if(heap[heap[A].l].dis<heap[heap[A].r].dis)swap(heap[A].l,heap[A].r);
heap[A].dis=heap[heap[A].r].dis+1;
return A;
}

long long Top(int x){return heap[x].v;}
void Pop(int &x){x=Merge(heap[x].l,heap[x].r);}

void dfs(int u){
root[u]=Newheap(ninja[u].c);
siz[u]=1;
sum[u]=ninja[u].c;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	dfs(v);
	sum[u]+=sum[v];
	siz[u]+=siz[v];
	root[u]=Merge(root[u],root[v]);
}
while(sum[u]>m){
	sum[u]-=Top(root[u]);
	Pop(root[u]);
	siz[u]--;
}
ans=max(ans,siz[u]*ninja[u].l);
}

int main(){
freopen("2809.in","r",stdin);
freopen("2809.out","w",stdout);
scanf("%d %lld",&n,&m);
heap[0].dis=-1;
for(int i=1;i<=n;i++){
	scanf("%d %lld %lld",&ninja[i].b,&ninja[i].c,&ninja[i].l);
    AddEdge(ninja[i].b,i);
}
dfs(1);
printf("%lld\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
10
2016
0

[BZOJ2733] [HNOI2012]永无乡

首先连通块我们用并查集维护,而查询k大我们用权值线段树维护

建边就是合并两个线段树

查询直接在权值线段树查询就好了

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

int n,m,q,a[100005],f[100005],v[100005],root[100005],cnt;

struct SegTree{
int nl,nr,sum;
}tree[2000005];

int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}

void Insert(int &rt,int l,int r,int pos){
if(!rt)rt=++cnt;
if(l==r){tree[rt].sum=1;return;}
int mid=l+r>>1;
if(pos<=mid)Insert(tree[rt].nl,l,mid,pos);
else Insert(tree[rt].nr,mid+1,r,pos);
tree[rt].sum=tree[tree[rt].nl].sum+tree[tree[rt].nr].sum;
}

int Query(int rt,int l,int r,int k){
if(l==r)return l;
int mid=l+r>>1;
if(tree[tree[rt].nl].sum>=k)return Query(tree[rt].nl,l,mid,k);
return Query(tree[rt].nr,mid+1,r,k-tree[tree[rt].nl].sum);
}

int Merge(int l,int r){
if(!l)return r;
if(!r)return l;
tree[l].nl=Merge(tree[l].nl,tree[r].nl);
tree[l].nr=Merge(tree[l].nr,tree[r].nr);
tree[l].sum=tree[tree[l].nl].sum+tree[tree[l].nr].sum;
return l;
}

int main(){
freopen("2733.in","r",stdin);
freopen("2733.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){scanf("%d",&a[i]);f[i]=i;}
for(int i=1;i<=m;i++){
	int tp,tq;
	scanf("%d %d",&tp,&tq);
	tp=Find(tp);tq=Find(tq);f[tp]=tq;
}
for(int i=1;i<=n;i++){Insert(root[Find(i)],1,n,a[i]);v[a[i]]=i;}
scanf("%d",&q);
while(q--){
	char s[5];
	int x,y;
	scanf("%s %d %d",s,&x,&y);
	if(s[0]=='B'){x=Find(x);y=Find(y);if(x!=y){f[x]=y;root[y]=Merge(root[x],root[y]);}}
	if(s[0]=='Q'){x=Find(x);if(tree[root[x]].sum>=y)printf("%d\n",v[Query(root[x],1,n,y)]);else puts("-1");}
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
10
2016
0

[BZOJ4444] [Scoi2015]国旗计划

树上倍增

首先剖环成2倍长的链

对于每一个士兵求他的下一个士兵应该选哪一个,记录进Next数组

注意此时Next数组形成了一棵树,然后树上倍增就可以了

#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
 
int n,m,Next[400005],cnt,ans[200005],fa[400005][20];
 
struct Soldier{
long long l,r;
int id;
friend bool operator<(Soldier A,Soldier B){return A.l<B.l;}
}sol[400005];
 
int main(){
freopen("4444.in","r",stdin);
freopen("4444.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
    int xl,xr;
    scanf("%d %d",&xl,&xr);
    if(xl<xr){
        sol[++cnt].l=xl;sol[cnt].r=xr;
        sol[cnt].id=i;
        sol[++cnt].l=xl+m;sol[cnt].r=xr+m;
    }
    else {
        sol[++cnt].l=xl;sol[cnt].r=xr+m;
        sol[cnt].id=i;
        sol[++cnt].l=xl+m;sol[cnt].r=xr+m+m;
    }
}
sol[0].r=21000000000000000ll;
sort(sol+1,sol+cnt+1);
int j=0;
for(int i=1;i<=cnt;i++){
    while(j<=cnt && sol[j].l<=sol[i].r)j++;
    Next[i]=j-1;
}
for(int i=cnt-1;i>=1;i--){
    fa[i][0]=Next[i];
    for(j=1;j<=19;j++)fa[i][j]=fa[fa[i][j-1]][j-1];
    if(sol[i].id){
        int tp=i;
        for(j=19;j>=0;j--){if(sol[fa[tp][j]].r-sol[i].l<m){ans[sol[i].id]+=1<<j;tp=fa[tp][j];}}
        ans[sol[i].id]+=2;
    }
}
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
6
2016
0

[UOJ164] 【清华集训2015】V

最近集训出了很多SGTB(SeGmentTree Beats!)的题目,所以被迫来学习这个冬令营上的黑科技。。

这题照着其他人写的程序理解了几个小时,然后自己写了一发居然是最快的。。。

记录一下自己对于这题的理解吧

输入的操作分别对应:

1.区间加

2.区间max(0,v)

3.区间赋值

4.询问单点值

5.询问单点历史最值

然后我一开始试图维护十来个标记然后暴力搞。。然后就不会了

然后膜了一下其他人的程序和lzz的冬令营课件,总算有了一点理解了

这题关键在于单点询问,所以我们仅仅把区间当成一整个标记,每次下传后就清零

然后问题在于两个操作:询问历史最值和区间max

我们先不管询问历史最值

其实我们进行一番转化后可以发现,其实123操作都可以对应到一个(x,y)(加上x对y取max)上(这是对于一个区间的标记)

1:区间加v -> (v,INF)

2:区间max(0,v) -> (v,0)

3.区间赋值为v -> (-INF,v);

这很显然吧。。

然后我们考虑两个标记的合并,这里我还是想了一下的

设旧标记为A,新标记为B

那么我们进行合并就变成了(A.x+B.x,max(A.y+B.x,B.y))

为什么是这样呢?

首先我们考虑如果A.x+B.x,那么就直接相当于普通线段树的Add操作,明显可行

而max(A.y+B.x,B.y)则表示如果旧标记产生的最大值为A.y,那么我们最终要取的值要么就是旧标记的A.y加上新标记要加上的值(因为旧标记可能取A.y),要么就是新标记要取的B.y(感觉我这句话比较意识流啊),当然是在这两个数里面选一个最大值了

于是我们就处理完了没有历史最值询问的操作

但是这题是有历史最值询问的。。好坑啊

那么我们考虑再加上两个标记mx,addmx表示当前区间的历史最值和要加上去的值的历史最值

那么我们继续考虑合并标记

同样,我们设(X,Y)表示mx和addmx两个值(偷懒),那么我们继续设以前的旧标记为A,用来更新旧标记的新标记为B

那么历史最值可以怎么构成?可以由旧标记的历史最值、新标记的历史最值,或者是旧标记的当前值加上新标记的的历史最大加值。

前两个很好理解,但是最后一个是什么意思呢?

首先,新标记的历史最大加值可以用这样一段话来叙述:“这一段区间曾经加过这么大的值”

那么我们每次拿旧标记当前的值加上新标记的历史最大加值,就意味着这个合并后的标记曾经在某个时刻达到了这个可能的最大值

因为每次更新标记时都是自顶向下,那么没有被更新的旧标记的值一定是当前值,如果被更改了那么之前一定在这里下传过标记,所以这样是对的

而我们再考虑addmx可以怎么构成

显然这个值可能的取值为:旧标记的addmx,新标记的addmx加上旧标记的add

为什么又是这么取值呢?

第一种情况显然。第二种情况因为新标记的历史最大加值此时没有经过任何更新,也就是和旧标记一点关联也没有

而因为add的定义和题目的描述(就是上面的小写标记),add标记一定不会小于0

那么我们当然需要加上这个add值(新标记此前不可能加过add标记),这样能让解更优

那么你可能会问:为什么不能让旧标记的历史最值加上新标记的add呢?

因为新标记是用来更新旧标记的,所以这样可能重复的加所以不行

这仅仅是个人的理解,我觉得真是漏洞百出,具体的证明lzz冬令营课件里面有,反正我没有看太懂。。。

我真是太弱了

这真是一篇意识流的题解

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

int n,m;
long long a[500005];
const long long INF=1000000000000000ll;

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

struct SegTree{
int l,r;
long long v,mx,add,addmx;
SegTree(){}
SegTree(long long V,long long MX,long long ADD,long long ADDMX){v=V;mx=MX;add=ADD;addmx=ADDMX;}
SegTree(int L,int R,long long V,long long MX,long long ADD,long long ADDMX){l=L;r=R;v=V;mx=MX;add=ADD;addmx=ADDMX;}
}tree[2000005],tmp;

SegTree Update(SegTree A,SegTree B){
return SegTree(A.l,A.r,max(A.v+B.add,B.v),max(max(A.mx,B.mx),A.v+B.addmx),max(A.add+B.add,-INF),max(A.addmx,A.add+B.addmx));
}

void Pushdown(int rt){
tree[rt*2]=Update(tree[rt*2],tree[rt]);
tree[rt*2+1]=Update(tree[rt*2+1],tree[rt]);
tree[rt]=SegTree(tree[rt].l,tree[rt].r,0,0,0,0);
}

void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r){
	tree[rt].addmx=tree[rt].add=tree[rt].v=tree[rt].mx=a[l];
	return;
}
int mid=l+r>>1;
Build(rt*2,l,mid);
Build(rt*2+1,mid+1,r);
}

void Change(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r){tree[rt]=Update(tree[rt],tmp);return;}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Change(rt*2,l,r);
if(r>mid)Change(rt*2+1,l,r);
}

long long Query(int rt,int pos,int id){
if(tree[rt].l==tree[rt].r){return id?tree[rt].mx:tree[rt].v;}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)return Query(rt*2,pos,id);
if(pos>mid)return Query(rt*2+1,pos,id);
}

int main(){
freopen("164.in","r",stdin);
freopen("164.out","w",stdout);
Read(n);Read(m);
for(int i=1;i<=n;i++)Read(a[i]);
Build(1,1,n);
for(int i=1;i<=m;i++){
    int opt,l,r,v;
    Read(opt);
    if(opt==1){Read(l);Read(r);Read(v);tmp=SegTree(0,0,v,v);Change(1,l,r);}
    if(opt==2){Read(l);Read(r);Read(v);tmp=SegTree(0,0,-v,-v);Change(1,l,r);}
    if(opt==3){Read(l);Read(r);Read(v);tmp=SegTree(v,v,-INF,-INF);Change(1,l,r);}
    if(opt==4){Read(v);printf("%lld\n",Query(1,v,0));}
    if(opt==5){Read(v);printf("%lld\n",Query(1,v,1));}
}
return 0;
}
Category: 其他OJ | Tags: OI uoj
4
3
2016
0

[BZOJ2179] FFT快速傅立叶

FFT模版题

话说网上对FFT讲的神乎其神,以后我来搞一份小学生都能看懂的FFT入门吧

最好没有公式和严谨的证明,搞一些非常通俗的就比较好

因为我自己也只会模版。。。

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

const int SIZE=300005;
const double Pi=acos(-1);

int An,Bn,Cn,n,Step,Rev[SIZE],Ans[SIZE];
char s[SIZE];

struct Complex{
double a,b;
Complex(double sa=0.0,double sb=0.0){a=sa;b=sb;}
friend Complex operator+(Complex a,Complex b){return Complex(a.a+b.a,a.b+b.b);}
friend Complex operator-(Complex a,Complex b){return Complex(a.a-b.a,a.b-b.b);}
friend Complex operator*(Complex a,Complex b){return Complex(a.a*b.a-a.b*b.b,b.a*a.b+a.a*b.b);}
}A[SIZE],B[SIZE],C[SIZE];

void FFT(Complex *x,int flag){
for(int i=0;i<n;i++)if(i<Rev[i])swap(x[i],x[Rev[i]]);
for(int k=1;k<n;k<<=1){
	Complex wk=Complex(cos(Pi/k),flag*sin(Pi/k));
	for(int i=0;i<n;i+=k<<1){
		Complex wkj=Complex(1.0,0.0);
		for(int j=0;j<k;j++){
			Complex a=x[i+j],b=x[i+j+k]*wkj;
			x[i+j]=a+b;
			x[i+j+k]=a-b;
			wkj=wkj*wk;
		}
	}
}
if(flag==-1)for(int i=0;i<n;i++)x[i].a/=n;
}

void Init_Solve_Out(){
scanf("%d",&An);
Bn=An;Cn=An+Bn-1;
scanf("%s",s);
for(int i=0;i<An;i++)A[i]=Complex(s[i]-'0');
scanf("%s",s);
for(int i=0;i<Bn;i++)B[i]=Complex(s[i]-'0');
for(n=1,Step=0;n<Cn;n<<=1,Step++);
for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));
FFT(A,1);FFT(B,1);
for(int i=0;i<n;i++)C[i]=A[i]*B[i];
FFT(C,-1);
for(int i=0;i<Cn;i++)Ans[Cn-i]=(int)(C[i].a+0.5);
for(int i=1;i<=Cn;i++)Ans[i+1]+=Ans[i]/10,Ans[i]%=10;
if(Ans[Cn+1])Cn++;
for(int i=Cn;i>=1;i--)printf("%d",Ans[i]);
}

int main(){
freopen("2179.in","r",stdin);
freopen("2179.out","w",stdout);
Init_Solve_Out();
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
31
2016
0

[UOJ34] 多项式乘法

第一道FFT

话说后缀数组我只会敲模版……这几天的比赛验证了我连暴力都能写挂

但是最近好像碰到好多FFT题目,于是就学习了一下

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

const double Pi=2*asin(1);
const int NUM_SIZE=100005;

int An,Bn,Cn,Rev[NUM_SIZE*3],Step,n;

struct Complex{
double a,b;
Complex(double as=0.0,double bs=0.0){a=as;b=bs;}
friend Complex operator+(Complex a,Complex b){return Complex(a.a+b.a,a.b+b.b);}
friend Complex operator-(Complex a,Complex b){return Complex(a.a-b.a,a.b-b.b);}
friend Complex operator*(Complex a,Complex b){return Complex(a.a*b.a-a.b*b.b,b.a*a.b+a.a*b.b);}
friend Complex operator/(Complex a,Complex b){return Complex((a.a*b.a+a.b*b.b)/(b.a*b.a+b.b*b.b),(b.a*a.b-a.a*b.b)/(b.a*b.a+b.b*b.b));}
double Mod(){return sqrt(a*a+b*b);}
}A[NUM_SIZE*3],B[NUM_SIZE*3],C[NUM_SIZE*3];

template<typename T>void Read(T &x){
int flag=1;
char ch;
while((ch=getchar())<'0' || ch>'9')if(ch=='-')flag=-1;
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
x*=flag;
}

void FFT(Complex *x,int flag){
for(int i=0;i<n;i++)if(i<Rev[i])swap(x[i],x[Rev[i]]);
for(int k=1;k<n;k<<=1){
    Complex wk=Complex(cos(Pi/k),flag*sin(Pi/k));
    for(int i=0;i<n;i+=k<<1){
		Complex wkj=Complex(1.0,0.0);
		for(int j=0;j<k;j++){
			Complex a=x[i+j],b=x[i+j+k]*wkj;
			x[i+j]=a+b;
			x[i+j+k]=a-b;
			wkj=wkj*wk;
		}
    }
}
if(flag==-1){for(int i=0;i<n;i++)x[i].a/=n;}
}

int main(){
freopen("34.in","r",stdin);
freopen("34.out","w",stdout);
Read(An);Read(Bn);
An++;Bn++;
Cn=An+Bn-1;
for(int i=0;i<An;i++)Read(A[i].a);
for(int i=0;i<Bn;i++)Read(B[i].a);
for(n=1,Step=0;n<Cn;Step++,n<<=1);
for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));
FFT(A,1);
FFT(B,1);
for(int i=0;i<n;i++)C[i]=A[i]*B[i];
FFT(C,-1);
for(int i=0;i<Cn;i++)printf("%d ",(int)(C[i].a+0.5));
putchar('\n');
return 0;
}
Category: 其他OJ | Tags: OI uoj
3
30
2016
0

[BZOJ3343] 教主的魔法

分块

每个块维护两个数组,一个是按位置排序,另一个按大小排序

修改暴力做两块,中间搞个tag

询问两块暴力,中间二分

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

int n,q,cnt;
const int block_size=1000,block_num=1000;

struct Block{
int block1[block_size+5],block2[block_size+5];
int n,tag;
}block[block_num+5];

void Add(int l,int r,int v){
int first_block=(l-1)/block_size+1,last_block=(r-1)/block_size+1,first_pos=(l-1)%block_size+1,last_pos=(r-1)%block_size+1;
if(first_block==last_block){
    for(int i=first_pos;i<=last_pos;i++)block[first_block].block1[i]+=v;
    for(int i=1;i<=block[first_block].n;i++)block[first_block].block2[i]=block[first_block].block1[i];
    sort(block[first_block].block2+1,block[first_block].block2+block[first_block].n+1);
	return;
}
for(int i=first_block+1;i<last_block;i++)block[i].tag+=v;
for(int i=first_pos;i<=block[first_block].n;i++)block[first_block].block1[i]+=v;
for(int i=1;i<=block[first_block].n;i++)block[first_block].block2[i]=block[first_block].block1[i];
sort(block[first_block].block2+1,block[first_block].block2+block[first_block].n+1);
for(int i=1;i<=last_pos;i++)block[last_block].block1[i]+=v;
for(int i=1;i<=block[last_block].n;i++)block[last_block].block2[i]=block[last_block].block1[i];
sort(block[last_block].block2+1,block[last_block].block2+block[last_block].n+1);
}

int Div(int id,int k){
int l=1,r=block[id].n,ans=0;
while(l<=r){
	int mid=l+r>>1;
	if(block[id].block2[mid]+block[id].tag<k){l=mid+1;ans=mid;}
	else {r=mid-1;}
}
return block[id].n-ans;
}

int Query(int l,int r,int k){
int first_block=(l-1)/block_size+1,last_block=(r-1)/block_size+1,first_pos=(l-1)%block_size+1,last_pos=(r-1)%block_size+1,ans=0;
if(first_block==last_block){
    for(int i=first_pos;i<=last_pos;i++)ans+=(k<=(block[first_block].block1[i]+block[first_block].tag));
	return ans;
}
for(int i=first_block+1;i<last_block;i++)ans+=Div(i,k);
for(int i=first_pos;i<=block[first_block].n;i++)ans+=(k<=(block[first_block].block1[i]+block[first_block].tag));
for(int i=1;i<=last_pos;i++)ans+=(k<=(block[last_block].block1[i]+block[last_block].tag));
return ans;
}

int main(){
freopen("3343.in","r",stdin);
freopen("3343.out","w",stdout);
scanf("%d %d",&n,&q);
cnt=(n-1)/block_size+1;
for(int i=1;i<cnt;i++)block[i].n=block_size;
block[cnt].n=(n-1)%block_size+1;
for(int i=1;i<=n;i++){
	int pos_block=(i-1)/block_size+1,pos=(i-1)%block_size+1;
	scanf("%d",&block[pos_block].block1[pos]);
}
for(int i=1;i<=cnt;i++){
	for(int j=1;j<=block[i].n;j++)block[i].block2[j]=block[i].block1[j];
	sort(block[i].block2+1,block[i].block2+block[i].n+1);
}
for(int i=1;i<=q;i++){
	int l,r,v;
	char s[5];
    scanf("%s %d %d %d",s,&l,&r,&v);
    if(s[0]=='M')Add(l,r,v);
    if(s[0]=='A')printf("%d\n",Query(l,r,v));
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
30
2016
0

初中OI生涯总结

忍不住感慨一下我初中的OI生涯了。。

回想初中我OI搞的惨不忍睹

当时没有老师,班主任和家长也不太资瓷

所以初一就浪掉了,水平=会写helloworld,当时考虑以后搞一搞高考

初二有了一个OI老师,感觉好一点了

还有教仪站的课,就有了两个OI老师(汪老师和贾老师)

但是当时一周一共就两次课,还有很多人不想学就在写作业讲话干扰别人,环境可谓十分恶劣,想听课也很难听的进去

初二上学期,我经历了一次至关重要的转变

我在某一次汪老师出的模拟赛AK了

而且那次就我一个AK,其他人基本都六七十分

所以我的心态就改变了

然后学习了一些高级算法但是因为文化课问题又停OI了

初三一年全部文化课然后一题没做

到了初三的暑假中考考完后……

发现下一届(就是现在初三)出现了好多大爷!

MedalPluS,ahwhzzt等等一大群神犇,水平不知道比我高到哪里去了

然后就方了,觉得今年被高二碾压,明年被高一碾压

然后进不了省队不就GG了吗

然后开始叹息痛恨于没有老师指点,环境十分恶劣

要是我初中去了27中也许水平就会变高不少?

我的下一届学弟都有了老师和稳定的刷题计划

学习环境也都变好了很多很多,至少会有学长djch等人教你们,上课也不会有一群人自己不听还去干扰你

而初三的我即使保送了FZ,但是还是因为班主任“你要拼中考”而放弃了一年OI,现在当然被虐惨了

wyx大爷初三就去FZ培训了……我还在学校玩泥巴

唉,毕竟都是往事,现在的我要为了明年的省队奋斗

不能被到时候的高一虐惨了然后没进省队就AFO了

总之还是要多做题提高实力啊

自己选择的路,跪着也要走完!

Bless All.

Category: 随笔 | Tags: 随笔
3
29
2016
0

[BZOJ1468] Tree

一模一样的点分治……

为了凑博客数又复制了一遍

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
  
int n,k,h[40005],en,mx[40005],siz[40005],ans,root,val,vis[40005],temp[40005],cnt;
  
struct Edge{
int b,v,next;
}e[80005];
  
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
  
void DfsSiz(int u,int fa){
siz[u]=1;
mx[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa && !vis[v]){
        DfsSiz(v,u);
        siz[u]+=siz[v];
        mx[u]=max(mx[u],siz[v]);
    }
}
}
  
void DfsRoot(int point,int u,int fa){
mx[u]=max(mx[u],siz[point]-siz[u]);
if(val>mx[u]){val=mx[u];root=u;}
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa && !vis[v])DfsRoot(point,v,u);
}
}
  
void GetDist(int u,int fa,int val){
temp[++cnt]=val;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa && !vis[v])GetDist(v,u,val+e[i].v);
}
}
  
int Cal(int u,int val){
cnt=0;
int now=0;
GetDist(u,u,val);
sort(temp+1,temp+cnt+1);
//for(int i=1;i<=cnt;i++)printf("Temp:%d\n",temp[i]);
int i=1,j=cnt;
while(i<j){
    while(temp[i]+temp[j]>k && i<j)j--;
    now+=j-i;
    i++;
}
//printf("Now:%d\n",now);
return now;
}
  
void Dfs(int u){
val=2100000000;
DfsSiz(u,u);
DfsRoot(u,u,0);
ans+=Cal(root,0);
//printf("Ans:%d\n",ans);
vis[root]=1;
for(int i=h[root];i;i=e[i].next){
    int v=e[i].b;
    if(!vis[v]){
        ans-=Cal(v,e[i].v);
        Dfs(v);
    }
}
}
  
int main(){
freopen("1468.in","r",stdin);
freopen("1468.out","w",stdout);
scanf("%d",&n);
//memset(h,0,sizeof(h));
//memset(vis,0,sizeof(vis));
//ans=en=0;
for(int i=1;i<n;i++){
    int sa,sb,sc;
    scanf("%d %d %d",&sa,&sb,&sc);
    AddEdge(sa,sb,sc);
    AddEdge(sb,sa,sc);
}
scanf("%d",&k);
Dfs(1);
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com