BZOJ 2938 病毒

发表于 2017-01-09 | 更新于 2018-06-17

Link

Solution

建立AC自动机，条件等价于沿着非单词节点走出一个环。这是比较显然的：走到了一个曾经到过的节点，就说明两次经过这个节点之间的字符串循环起来就符合题意了。

Tips

又被自己乱想的不存在的边界情况卡住了。以后如果对自己的想法有什么异议，一定要造出具体到数据的反例。

Code

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=30000+10;
namespace AC
{
	const int SIZE=MAXN;
	struct Node
	{
		Node *son[2],*fail,*last;
		int cnt;
		Node(){cnt=0;son[0]=son[1]=fail=last=0;}
		Node *&next(char c){return son[c-'0'];}
		int num();
	}*ME=(Node*)malloc(SIZE*sizeof(Node)),*POOL=ME,*root=new Node;
	Node *newNode() {return new(ME++) Node;}
	int Node::num(){return this-POOL+1;}
	void Insert(char *s)
	{
		Node *cur=root;
		for(int i=1,L=strlen(s+1);i<=L;i++)
		{
			if(!cur->next(s[i])) cur->next(s[i])=newNode();
			cur=cur->next(s[i]);
		}
		cur->cnt++;
	}
	void Build()
	{
		static Node *Q[SIZE];int he=1,ta=0;
		root->fail=root;root->last=0;
		for(char c='0';c<='1';++c)
			if(!root->next(c)) root->next(c)=root;
			else
			{
				root->next(c)->fail=root;
				root->next(c)->last=0;
				Q[++ta]=root->next(c);////root;
			}
		while(he<=ta)
		{
			Node *cur=Q[he++];
			for(char c='0';c<='1';++c)
			{
				Node *&son=cur->next(c);
				if(!son) son=cur->fail->next(c);
				else
				{
					son->fail=cur->fail->next(c);
					son->last=son->fail->cnt?son->fail:son->fail->last;
					Q[++ta]=son;
				}
			}
		}
	}
}
using namespace AC;
struct Edge{int to,pre;}e[SIZE<<2];int id[SIZE],ec;
void Adde(int f,int t){e[++ec].to=t;e[ec].pre=id[f];id[f]=ec;}
bool DAG()
{
	static int Q[SIZE],he,ta,deg[SIZE];
	int n=ME-POOL;he=1,ta=0;
	for(Node *ptr=POOL;ptr!=ME;++ptr)
		for(char c='0';c<='1';++c)
			if(!ptr->next(c)->cnt && !ptr->next(c)->last)
			{
				Adde(ptr->num(),ptr->next(c)->num());
				deg[ptr->next(c)->num()]++;
			}
	for(int i=1;i<=n;i++)
		if(!deg[i]) Q[++ta]=i;
	while(he<=ta)
	{
		int cur=Q[he++];
		for(int i=id[cur];i;i=e[i].pre)
		{
			int u=e[i].to;
			deg[u]--;
			if(!deg[u])
				Q[++ta]=u;
		}
	}
	return ta==n;
}
int main()
{
	freopen("input","r",stdin);
	static char s[MAXN];
	int n;get(n);
	for(int i=1;i<=n;i++)
		scanf("%s",s+1),Insert(s);
	Build();
	puts(DAG()?"NIE":"TAK");
	return 0;
}
/* AC Record(Bugs) *
 * WA ptr->next(c)->last 
 * * * * * * * * * */

BZOJ 2434 ali的打字机

发表于 2017-01-09 | 更新于 2018-06-17

Link

Solution

Fail树。子树和。经典思路。

Tips

AC自动机好像用到了不少记录某个字符匹配到哪个状态的情况啊。一开始太naive，直接暴力插入暴力查询，时间爆炸了。

Code

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=1e5+10;
namespace AC
{
	const int SIGMA=26;
	const int SIZE=MAXN<<3;
	struct Node
	{
		Node *son[SIGMA],*fail,*last;int cnt;
		Node *&next(char c){return son[c-'a'];}
		int num();
	}*ME=(Node*)malloc(SIZE*sizeof(Node)),*HEAD=ME;
	int Node::num(){return this-HEAD+1;}
	Node *newNode()
	{
		static Node *cur;
		cur=ME++;cur->fail=cur->last=0;cur->cnt=0;
		memset(cur->son,0,sizeof(cur->son));return cur;
	}
	struct AC
	{
		Node *root;
		AC(){root=newNode();}
		void Build()
		{
			static Node *Q[SIZE];static int he,ta;
			he=1,ta=0;root->last=0;root->cnt=0;root->fail=root;
			for(char c='a';c<='z';++c)
				if(!root->next(c)) root->next(c)=root;
				else
				{
					root->next(c)->fail=root;
					root->next(c)->last=0;
					Q[++ta]=root->next(c);
				}
			while(he<=ta)
			{
				Node *cur=Q[he++];
				for(char c='a';c<='z';++c)
				{
					Node *&son=cur->next(c);
					if(!son) son=cur->fail->next(c);
					else
					{
						son->fail=cur->fail->next(c);
						son->last=son->fail->cnt?son->fail:son->fail->last;
						Q[++ta]=son;
					}
				}
			}
		}
	}mata;
}
using namespace AC;
struct Edge{int to,pre;}e[MAXN<<1];int ec,id[MAXN];
void Adde(int f,int t)
{
	e[++ec].to=t;e[ec].pre=id[f];id[f]=ec;
	e[++ec].to=f;e[ec].pre=id[t];id[t]=ec;
}
void BuildTree()
{
	for(Node *ptr=HEAD;ptr!=ME;++ptr)
		Adde(ptr->num(),ptr->fail->num());
}
int dfs[SIZE],dc,li[SIZE],ro[SIZE];
void DFS(int pos)
{
	dfs[li[pos]=++dc]=pos;
	for(int i=id[pos];i;i=e[i].pre)
	{
		int u=e[i].to;
		if(li[u]) continue;
		DFS(u);
	}
	ro[pos]=dc;
}
struct Bit
{
	int n,a[SIZE];
	#define lowbit(x) (x & -x)
	int Sum(int pos)
	{
		int res=0;
		for(;pos;pos-=lowbit(pos)) 
			res+=a[pos];
		return res;
	}
	void Add(int pos,int v)
	{
		if(!pos) return;
		for(;pos<=n;pos+=lowbit(pos)) 
			a[pos]+=v;
	}
	int Sum(int l,int r){return Sum(r)-Sum(l-1);}
	#undef lowbit
}bit;
struct List{int to,id,pre;}q[MAXN];int qc,head[MAXN],ANS[MAXN];
void Addq(int f,int t,int id){q[++qc].to=t;q[qc].id=id;q[qc].pre=head[f];head[f]=qc;}
int main()
{
	freopen("input","r",stdin);
	static char str[MAXN],*cptr=str,now[MAXN],*nptr=now;
	static Node *ref[MAXN],*state[MAXN];int sc=0;
	scanf("%s",str);
	state[0]=mata.root;
	for(cptr=str;*cptr;++cptr)
	{
		Node *cur=state[nptr-now];
		if(*cptr=='B')	*nptr--=0;//--nptr;
		else if(*cptr=='P') ref[++sc]=cur;
		else
		{
			*++nptr=*cptr;
			if(!cur->next(*nptr)) cur->next(*nptr)=newNode();
			cur=cur->next(*nptr);
			state[nptr-now]=cur;
		}
	}
	mata.Build();
	BuildTree();
	int root=mata.root->num();
	DFS(root);bit.n=dc;
	int m;get(m);
	for(int i=1;i<=m;i++)
	{
		int x,y;get(x),get(y);
		Addq(y,x,i);
	}
	while(nptr!=now) *nptr--=0;
	for(sc=0,cptr=str;*cptr;++cptr)
	{
		Node *cur=state[nptr-now];
		if(*cptr=='B')
		{
			*nptr--=0;
			bit.Add(li[cur->num()],-1);
		}
		else if(*cptr=='P')
		{
			++sc;
			for(int i=head[sc];i;i=q[i].pre)
			{
				int u=ref[q[i].to]->num();
				ANS[q[i].id]=bit.Sum(li[u],ro[u]);
			}
		}
		else
		{
			*++nptr=*cptr;
			state[nptr-now]=cur=cur->next(*nptr);
			bit.Add(li[cur->num()],1);
		}
	}	
	for(int i=1;i<=m;i++) printf("%d\n",ANS[i]);
	return 0;
}
/* AC Record(Bugs) *
 * WA sizeof array too small (turned out to be no problem)
 * WA printf %s error ---> printfing char*,deleted words must be cleared
 * MLE using list to contain,maybe n^2
 * WA in the for-loop below nptr wasn't reset
 *	  AND the characters in now[]wasn't cleared same as above
 * TLE Forever loop-->not forever
 *		the Inserting is too slow..too simple..
 *		the Matching is too slow..too simple..
 * * * * * * * * * */

BZOJ3942 && 3940 Censoring

发表于 2017-01-09 | 更新于 2018-06-17

Link And This

Solution

每加入一个字符，用栈记录匹配到的位置。删除后缀就通过弹栈回到之前相应的位置实现

Code

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=1e5+10;
namespace AC
{
	struct Node
	{
		Node *son[26],*fail,*last;
		int len;
		Node(){memset(son,0,sizeof(son));fail=last=0;len=0;}
		Node *&next(char c){return son[c-'a'];}
	}*root=new Node;
	Node *newNode()
	{
		static int SIZE=MAXN;
		static Node *ME=(Node*)malloc(SIZE*sizeof(Node)),*cur;
		cur=ME++;memset(cur->son,0,sizeof(cur->son));cur->last=cur->fail=0;
		cur->len=0;return cur;
	}
	void Insert(char *s)
	{
		Node *cur=root;
		int len=strlen(s+1);
		for(int i=1;i<=len;++i)
		{
			if(cur->next(s[i])) cur=cur->next(s[i]);
			else cur->next(s[i])=newNode(),cur=cur->next(s[i]);
		}
		assert(cur->len==0);
		cur->len=len;
	}
	void Build()
	{
		static Node *Q[MAXN];int he=1,ta=0;
		for(char c='a';c<='z';++c)
		{
			Node *&son=root->next(c);
			if(!son) son=root;
			else
			{
				son->fail=root;
				son->last=0;
				Q[++ta]=son;
			}
		}
		while(he<=ta)
		{
			Node *cur=Q[he++];
			for(char c='a';c<='z';++c)
			{
				Node *&son=cur->next(c);
				if(!son)
					son=cur->fail->next(c);
				else
				{
					son->fail=cur->fail->next(c);
					son->last=son->fail->len?son->fail:son->fail->last;
					Q[++ta]=son;
				}
			}
		}
	}
};
using namespace AC;
int main()
{
	//freopen("input","r",stdin);
	static char str[MAXN],S[MAXN],T[MAXN];
	static Node *f[MAXN];
	scanf("%s",S+1);int n;get(n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",T+1);
		Insert(T);
	}
	Build();
	int len=0;f[0]=root;
	for(int i=1,L=strlen(S+1);i<=L;i++)
	{
		str[++len]=S[i];
		f[len]=f[len-1]->next(S[i]);
		if(f[len]->len) 
			len-=f[len]->len;//assert(cur->lens.size()==1);
		else if(f[len]->last) 
			len-=f[len]->last->len;//assert(cur->last->.size()==1);
	}
	str[len+1]=0;
	printf("%s\n",str+1);
	return 0;
}
/* AC Record(Bugs) *
 * WA 
 * * * * * * * * * */

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=1e6+10;
int main()
{
	//freopen("input","r",stdin);
	static char S[MAXN],T[MAXN],dest[MAXN];
	static int p[MAXN],f[MAXN],len;
	scanf("%s%s",S+1,T+1);
	int s=strlen(S+1),t=strlen(T+1);
	p[1]=0;
	for(int i=2,j;i<=t;i++)
	{
		j=p[i-1];
		while(j && T[j+1]!=T[i]) j=p[j];
		if(T[j+1]==T[i]) j++;
		p[i]=j;
	}
	
	for(int i=1,j;i<=s;i++)
	{
		dest[++len]=S[i];
		j=f[len-1];
		while(j && T[j+1]!=S[i]) j=p[j];
		if(T[j+1]==S[i]) j++;
		if(j==t) len-=t;
		else f[len]=j;
	}
	dest[len+1]=0;
	printf("%s\n",dest+1);
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */

BZOJ 3196 二x平衡树

发表于 2017-01-09 | 更新于 2018-06-17

Link

Solution

外层区间线段树，内层平衡树存数值。K值用到二分答案，比较经典。之前写过，为了试试新的代码写法，写了一遍。结果Treap旋转的时候没有更新信息，WA了一次。

Code

treap在trans的时候没有pushup

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d\n",x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=50000+10,INF=0x1f1f1f1f;
using std::max;
using std::min;
namespace IO
{
	#ifndef get
	const int INBUF=1e6;
	char in[INBUF],*iptr=in,*iend=in;
	#define getc() ( (iptr==iend && (iend=(iptr=in)+fread(in,1,INBUF,stdin),iptr==iend))?EOF:*iptr++ )
	inline void get(int &x)
	{
		static int f,ch;
		f=1;
		while(!isdigit(ch=getc())) if(ch=='-') f=-1;
		x=ch-'0';
		while(isdigit(ch=getc())) (x*=10)+=ch-'0';
		x*=f;
	}
	#endif
	#ifndef put
	const int OUTBUF=1e6;
	char out[OUTBUF],*optr=out,*oend=out+OUTBUF-1;
	#define putc(x) (optr==oend?(fwrite(out,1,optr-out,stdout),optr=out,*optr++=(x)):*optr++=(x))
	inline void put(int x)
	{
		if(x==0) putc('0');
		if(x<0) putc('-'),x=-x;
		if(x)
		{
			static int stack[100],*top=stack;
			while(x) *++top=x%10,x/=10;
			while(top!=stack) putc((*top--)+'0');
		}
		putc('\n');
	}
	#endif
	void flush()
	{
		#ifndef put
		fwrite(out,1,optr-out,stdout);
		#endif
	}
}
using namespace IO;

namespace Treap
{
	const int P=1e5+7;
	struct Node
	{
		Node *son[2];
		int v,py,sz,cnt;
		Node(){py=P;sz=0;}
		void up(){sz=cnt+son[0]->sz+son[1]->sz;}
		int LowCount(int);
		int Pred(int);
		int Succ(int);
	}*null=new Node;

	void out(Node *pos)
	{
		if(pos==null) return;
		out(pos->son[0]);printf("%d(%d)  ",pos->v,pos->cnt);out(pos->son[1]);
	}

	Node *newNode(int v)
	{
		static const int SIZE=MAXN*30;
		static Node *ME=(Node*)malloc(SIZE*sizeof(Node)),*cur;
		cur=ME++;cur->v=v;cur->py=rand()%P;cur->cnt=cur->sz=1;
		cur->son[0]=cur->son[1]=null;
		return cur;
	}
	void trans(Node *&pos,int d)
	{
		Node *s=pos->son[d];
		pos->son[d]=s->son[!d];s->son[!d]=pos;
		pos->up(),s->up();
		pos=s;
	}
	int adjust(Node *&pos)
	{
		int d=pos->son[0]->py>pos->son[1]->py;
		if(pos->py>pos->son[d]->py) trans(pos,d),d^=1;
		else d=-1;return d;
	}
	void Insert(Node *&pos,int v)
	{
		if(pos==null) pos=newNode(v);
		else if(pos->v==v) pos->cnt++,pos->up();
		else
		{
			Insert(pos->son[pos->v<v],v),pos->up();
			adjust(pos);
		}
	}
	int Node::LowCount(int v)
	{
		Node *pos=this;int res=0;
		while(pos!=null)
		{
			if(pos->v<v) res+=pos->son[0]->sz+pos->cnt,pos=pos->son[1];
			else pos=pos->son[0];
		}
		return res;
	}
	int Node::Pred(int v)
	{
		Node *pos=this;int res=-INF;
		while(pos!=null)
		{
			if(pos->v<v) chkmx(res,pos->v),pos=pos->son[1];
			else pos=pos->son[0];
		}
		return res;
	}
	int Node::Succ(int v)
	{
		Node *pos=this;int res=INF;
		while(pos!=null)
		{
			if(pos->v>v) chkmn(res,pos->v),pos=pos->son[0];
			else pos=pos->son[1];
		}
		return res;
	}
	void DelNode(Node *&pos)
	{
		int d=adjust(pos);
		if(~d)
		{
			assert(pos!=null);
			DelNode(pos->son[d]),pos->up();
		}
		else pos=null;
	}
	void Delete(Node *&pos,int v)
	{
		if(pos->v==v)
		{
			pos->cnt--,pos->up();
			if(!pos->cnt)
				pos->py=P,DelNode(pos);
		}
		else
		{
			Delete(pos->son[pos->v<v],v),pos->up();
			assert(adjust(pos)==-1);
		}
	}
}
using namespace Treap;
struct Data
{
	int cnt,pred,succ;
	Data(int cnt=0,int pred=-INF,int succ=INF):cnt(cnt),pred(pred),succ(succ){}
}nData;
Data Merge(Data a,Data b){return Data(a.cnt+b.cnt,max(a.pred,b.pred),min(a.succ,b.succ));}
namespace Seg
{
	typedef Treap::Node tNode;
	struct Node
	{
		Node *son[2];
		tNode *treap;
	}*null=new Node,*root=null;int TL,TR;
	Node *newNode()
	{
		static int SIZE=MAXN<<2;
		static Node *ME=(Node*)malloc(SIZE*sizeof(Node)),*cur;
		cur=ME++;cur->son[0]=cur->son[1]=null;cur->treap=Treap::null;
		return cur;
	}
	void Add(Node *&pos,int L,int R,int goal,int v)
	{
		if(pos==null) pos=newNode();
		Insert(pos->treap,v);
		if(L!=R)
		{
			int MID=(L+R)>>1;
			if(goal<=MID) Add(pos->son[0],L,MID,goal,v);
			else Add(pos->son[1],MID+1,R,goal,v);
		}
	}
	Data Access(Node *pos,int L,int R,int l,int r,int v)
	{
		if(L==l && R==r) return Data(pos->treap->LowCount(v),pos->treap->Pred(v),pos->treap->Succ(v));
		else
		{
			int MID=(L+R)>>1;
			if(r<=MID) return Access(pos->son[0],L,MID,l,r,v);
			else if(MID+1<=l) return Access(pos->son[1],MID+1,R,l,r,v);
			else return Merge(Access(pos->son[0],L,MID,l,MID,v),Access(pos->son[1],MID+1,R,MID+1,r,v));
		}
	}
	void Edit(Node *&pos,int L,int R,int goal,int ori,int v)
	{
		Delete(pos->treap,ori);
		Insert(pos->treap,v);
		if(L!=R)
		{
			int MID=(L+R)>>1;
			if(goal<=MID) Edit(pos->son[0],L,MID,goal,ori,v);
			else Edit(pos->son[1],MID+1,R,goal,ori,v);
		}
	}
}
using namespace Seg;
int a[MAXN];
int Kth(int l,int r,int K)
{
	int L=0,R=1e8,res;K--;
	while(L!=R)
	{
		int MID=(L+R+1)>>1;
		if((res=Access(root,TL,TR,l,r,MID).cnt)<=K) L=MID;
		else R=MID-1;
	}
	return L;
}
int main()
{
	freopen("input","r",stdin);
	int n,m;get(n),get(m);TL=1,TR=n;
	for(int i=1;i<=n;i++) get(a[i]),Add(root,TL,TR,i,a[i]);
	for(int i=1;i<=m;i++)
	{
		int opt,pos,l,r,k;
		get(opt);
		if(opt==3) get(pos),get(k);
		else get(l),get(r),get(k);
		switch(opt)
		{
			case 1:put(Access(root,TL,TR,l,r,k).cnt+1);break;
			case 2:put(Kth(l,r,k));break;
			case 3:Edit(root,TL,TR,pos,a[pos],k);a[pos]=k;break;
			case 4:put(Access(root,TL,TR,l,r,k).pred);break;
			case 5:put(Access(root,TL,TR,l,r,k).succ);break;
		}
	}
	flush();
	return 0;
}
/* AC Record(Bugs) *
 * WA trans pushup
 * * * * * * * * * */

被封装强迫症克小记

发表于 2017-01-07 | 更新于 2018-06-18

这篇的所有内容纯属一个超级蒟蒻的自言自语。 今天做一道树剖题，看完题目之后想到了一种很诡的做法：

在每条链上挂一个Treap，里面装这个链上含有的线段树的根节点。

（你笑笑说直接全局建线段树就行了，不需要每个点建一个，但我太蒟蒻，怎么研究过那种写法）于是就很愉快地开始写数据结构这样存储

1 2	struct TreapNode; struct SegNode;

然后发现，这样做，每次进行操作要传递很多可以不传递的变量，比如

1	SegTree.Access(root,1,PathSize,Rank(pos),PathSize);

前三个都是与此次操作无关的。写完A掉之后，感觉不爽。于是重新设计重写。

struct Treap;
{
	struct TreapNode;
};
struct Seg;
{
	struct SegNode;
};

发现这样做比原来的写法在实现数据结构上麻烦了不少，就比如需要四种null，重名了，只好改成nullSeg什么的。而且struct套struct写起来各种坑。 A掉之后，感觉不爽。于是开始研究stl的写法。。发现stl_tree.h中定义的_Rb_tree是这样的

struct _Rb_tree_node;
class _Rb_tree
{
    _Rb_tree_node ...;
};

感觉不错。于是写写写，写完之后，感觉好些了。然后看到Sengxian大神的代码，发现好多namespace啊试了试，发现namespace确实好，用着很舒服。。其中一个好就是null不会重复了。。于是我的数据结构就变成了这样

namespace Treap
{
    struct Node;
    struct Treap
    {
        Node ...;
    };
}

以后就这么写了。。。这两天状态很差，明天一定要加油了。

BZOJ 3529 数表

发表于 2017-01-05 | 更新于 2018-06-18

Link

Solution

定义 $F(i)$ 为 $i$ 的约数和，则 $F(i)$ 可以 $O(n\log n)$ 求出。Po姐的代码好象是线性筛？？OTZ。要求的是

嗯，先不考虑 $>a$ 的限制。考虑每个数字 $x$ 作为 $\gcd$ 对答案的贡献。有

P(x)=F(x)\times c(x)

其中 $c(x)$ 为 $\gcd(i,j)==x$ 的对数。而

c(x)=\sum_{x|d}\mu(\dfrac dx)[\dfrac nd][\dfrac md]

于是，

Ans=\sum_x P(x)=\sum_x \{F(x)\sum_{x|d}\mu(\dfrac dx)[\dfrac nd][\dfrac md]\}

又见熟悉的分块加速项，把求和式改成枚举 $d$ ，则

Ans=\sum_d [\dfrac nd][\dfrac md]\sum_{x|d}F(x)\mu(\dfrac dx)

后面的项是可以暴力前缀和的。有了 $a$ 的限制，就需要让所有 $>a$ 的 $F(i)$ 不被算进去。于是就用树状数组，动态地加入 $F(i)$ 。为了保证复杂度，把询问离线，按照 $a$ 排序，然后依次处理，可以保证修改树状数组的复杂度为 $O(n\log n)$

Tips

对2的整次幂取模，可以用&。

Code

//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int N=1e5,MAXN=N+10;
typedef long long LL;
using std::pair;
using std::sort;
using std::swap;
using std::min;

pair<int,int> F[MAXN],*curF;
int mu[MAXN],prime[MAXN],pcnt;
void Shake()
{
	static bool notp[MAXN];
	mu[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!notp[i])
			prime[++pcnt]=i,mu[i]=-1;
		for(int j=1;j<=pcnt && prime[j]*i<=N;j++)
		{
			notp[prime[j]*i]=1;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;
				break;
			}
			else
				mu[i*prime[j]]=-mu[i];
		}
	}
	for(int i=1;i<=N;i++)
	{
		F[i].second=i;
		for(int j=i;j<=N;j+=i)
			F[j].first+=i;
	}
	sort(F+1,F+1+N);F[N+1].first=2e9;
	curF=F+1;
}
struct BIT
{
	#define lowbit(x) (x & -x)
	int a[MAXN];
	int sum(int pos)
	{
		if(!pos) return 0;
		int res=0;
		for(;pos;pos-=lowbit(pos))
			res+=a[pos];
		return res;
	}
	int sum(int l,int r){return sum(r)-sum(l-1);}
	void add(int pos,int v)
	{
		if(!pos) assert(1);
		for(;pos<=N;pos+=lowbit(pos))
			a[pos]+=v;
	}
	#undef lowbit
}bit;
void Add(pair<int,int> *p)
{
	for(int i=p->second;i<=N;i+=p->second)
		bit.add(i,p->first*mu[i/p->second]);
}
int Calc(int n,int m)
{
	int res=0;
	if(n>m) swap(n,m);
	for(int i=1,last;i<=n;i=last+1)//+=..
	{
		last=min(n/(n/i),m/(m/i));
		res+=bit.sum(i,last)*(n/i)*(m/i);
	}
	return res;
}
struct Opt
{
	int n,m,a,id;
	bool operator <(const Opt &x) const{return a<x.a;}
}opt[MAXN];
int main()
{
	freopen("input","r",stdin);
	Shake();
	static int ANS[MAXN];
	int T;red(T);
	for(int i=1;i<=T;i++)
	{
		red(opt[i].n),red(opt[i].m),red(opt[i].a);
		opt[i].id=i;
	}
	sort(opt+1,opt+1+T);
	for(int i=1;i<=T;++i)
	{
		while(curF->first<=opt[i].a)
			Add(curF++);
		ANS[opt[i].id]=Calc(opt[i].n,opt[i].m)&0x7FFFFFFF;
	}
	for(int i=1;i<=T;i++) printf("%d\n",ANS[i]);
	return 0;
}

BZOJ2820 YY的GCD

发表于 2017-01-05 | 更新于 2018-06-18

Link

Solution

定义 $F(x)$ 为 $x|gcd(a,b)$ 的对数 $f(x)$ 为 $gcd(a,b)==x$ 的对数则

F(x)=[\dfrac nx][\dfrac mx]=\sum_{x|d}f(d)

f(x)=\sum_{x|d}\mu(\dfrac dx)F(d)=\sum_{x|d}\mu(\dfrac dx)[\dfrac nd][\dfrac md]

按照套路，一般把 $x$ 提出来可以简化问题于是

f(1)=\sum_{1|d}\mu(d)F(d)=\sum_{1|d}\mu(d)[\dfrac n{xd}][\dfrac m{xd}]

要求的是

\sum_{p\in P}f(p)=\sum_{p\in P}\sum_{1|d}\mu(d)F(d)

=\sum_{p\in P}\sum_{1|d}\mu(d)[\dfrac n{pd}][\dfrac m{pd}]

数据规模决定不能分别枚举一遍 $p,d$ 。看到这个式子长得比较可爱，令 $T=pd$ ，则问题变成了

\sum_T(\sum_{p|T}\mu(\dfrac Tp)[\dfrac nT][\dfrac mT])

于是，看到了熟悉的可以分块加速的项，思考能不能把

\sum_{p|T}\mu(\dfrac Tp)

弄出个前缀和。然后这是可以暴力求的。

Code

//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int N=10000000,MAXN=N+10;
typedef long long LL;
using std::swap;
using std::min;

LL Sum[MAXN];
int mu[MAXN],prime[MAXN],pcnt;
void Shake()
{
	static bool notp[MAXN];
	mu[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!notp[i])
		{
			prime[++pcnt]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=pcnt && prime[j]*i<=N;j++)
		{
			notp[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;
				break;
			}
			else
				mu[i*prime[j]]=-mu[i];
		}
	}
	for(int i=1;i<=pcnt;i++)
		for(int p=prime[i];p<=N;p+=prime[i])
			Sum[p]+=mu[p/prime[i]];
	for(int i=1;i<=N;i++)
		Sum[i]+=Sum[i-1];
}
LL Calc(int n,int m)
{
	LL res=0;
	if(n>m) swap(n,m);
	for(int l=1,r;l<=n;l=r+1)
	{
		r=min(n/(n/l),m/(m/l));
		res+=(Sum[r]-Sum[l-1])*(n/l)*(m/l);
	}
	return res;
}
int main()
{
	freopen("input","r",stdin);
	Shake();
	int T;red(T);
	while(T--)
	{
		int n,m;red(n),red(m);
		printf("%lld\n",Calc(n,m));
	}
	return 0;
}

BZOJ 2301 Problem b

发表于 2017-01-05 | 更新于 2018-06-17

Link

Solution

裸的反演

Code

//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int N=5e4,MAXN=N+10;
typedef long long LL;
using std::min;
using std::swap;
int mu[MAXN],prime[MAXN],pcnt,Mu[MAXN];
void Prep()
{
	static bool notp[MAXN];
	mu[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!notp[i])
		{
			prime[++pcnt]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=pcnt && prime[j]*i<=N;j++)
		{
			notp[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;
				break;
			}
			else
				mu[i*prime[j]]=-mu[i];
		}
	}
	for(int i=1;i<=N;i++) Mu[i]=Mu[i-1]+mu[i];
}
LL Count(int x,int y)//互质的个数
{
	LL res=0;
	if(x>y) swap(x,y);
	for(int i=1,last=1;i<=x;i=last+1)
	{
		last=min(x/(x/i),y/(y/i));
		res+=(LL)(Mu[last]-Mu[i-1])*(x/i)*(y/i);
	}
	return res;
}
int main()
{
	//freopen("input","r",stdin);
	Prep();
	int T;red(T);
	while(T--)
	{
		int a,b,c,d,K;red(a),red(b),red(c),red(d),red(K);
		printf("%lld\n",Count(b/K,d/K)+Count((a-1)/K,(c-1)/K)-Count((a-1)/K,d/K)-Count(b/K,(c-1)/K));
	}
	return 0;
}

BZOJ 2726 任务安排

发表于 2017-01-05 | 更新于 2018-06-18

又被克了很长时间官方数据有误？

Link

Solution

DP方程为 $f(i)=min\{f(j-1)+[S+cT(j,i)]\times cF(j,n) | j<=i\}$ $cT,cF$ 分别表示相应量的区间和 $j<k$ 且 $j$ 优于 $k$ 当且仅当 $\dfrac {[f(j-1)+(S-T_{j-1})(F_n-F_{j-1})]-[f_{k-1}+(S-T_{k-1})(F_n-F_{k-1})]}{F_{j-1}-F_{k-1}}>T_i$ $T,F$ 表示相应量的前缀和一开始没变号。。抓瞎了。。如果 $T_i$ 递增的话，就可以单调队列维护一个下凸壳。 $T_i$ 不递增，没办法，只能CDQ或者平衡树。 CDQ做法：分治之前按照 $T_i$ 排序，分治的每层把前半部分挑出来分治下去，回溯的时候按照 $id$ 的大小merge。然后就可以单调队列了。

Tips

判上下凸最好用叉积，就不用讨论x为0之类的。比较斜率与一个数最好讨论 $x$ 的符号，通过移项，相应变号，避免除法。因为这个WA了很长时间。还有，第一次编译一定要-Wall！！（Windows需要alias可以用doskey实现）

Code

//Code by Lucida
#include<bits/stdc++.h>
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
template <class T> inline void red(T &x)
{
	static int f,ch;
	f=1;
	while(!isdigit(ch=getchar()))
		if(ch=='-') f=-1;
	x=ch-'0';
	while(isdigit(ch=getchar()))
		(x*=10)+=ch-'0';
	x*=f;
}
typedef long long LL;
typedef long long ld;
using std::merge;
using std::sort;
using std::copy;

const int MAXN=300000+10;
LL f[MAXN],cx[MAXN],cy[MAXN];
LL F[MAXN],T[MAXN],n,S;

struct point
{
	LL x,y;int id;
	point(){}
	point(LL _x,LL _y,int _id=0):x(_x),y(_y),id(_id){}
};
point operator -(point a,point b){return point(a.x-b.x,a.y-b.y);}
bool operator <=(point a,LL b)
{
	return a.x>0?a.y-(ld)a.x*b<=0:
				 a.y-(ld)a.x*b>=0;
}
ld outer(point a,point b){return (ld)a.x*b.y-(ld)a.y*b.x;}
struct Opt
{
	int id;LL T;
	bool operator <(Opt a){return id<a.id;}
}p[MAXN],t[MAXN];
bool cmpT(Opt a,Opt b){return a.T<b.T;}
void partition(int l,int r,int midv)
{
	int pl=l,pr=(l+r)/2+1;
	for(int i=l;i<=r;i++)
		if(p[i].id<=midv) t[pl++]=p[i];
		else t[pr++]=p[i];
	copy(t+l,t+r+1,p+l);
}
void DC(int l,int r)
{
	static point Q[MAXN];
	int head,tail;
	if(l==r)
	{
		int i=l,j=l;
		chkmn(f[i],f[j-1]+cy[j]+T[i]*(F[n]-F[j-1]));
		return;
	}
	int mid=(l+r)/2;
	partition(l,r,mid);
	DC(l,mid);
	head=1,tail=0;
	#define count(a,b) (b-a+1)
	for(int pl=l;pl<=mid;pl++)
	{
		point cur=point(cx[pl],f[pl-1]+cy[pl],pl);
		while(count(head,tail)>=2 && outer(cur-Q[tail-1],Q[tail]-Q[tail-1])>=0)//(cur-Q[tail])<=(Q[tail]-Q[tail-1]))
			tail--;
		Q[++tail]=cur;
	}
	for(int pr=mid+1;pr<=r;pr++)
	{
		if(pr<r) assert(p[pr].T<=p[pr+1].T);
		while(count(head,tail)>=2 && (Q[head]-Q[head+1])<=p[pr].T) 
			head++;
		int i=p[pr].id,j=Q[head].id;
		chkmn(f[i],f[j-1]+cy[j]+T[i]*(F[n]-F[j-1]));
	}
	#undef count
	DC(mid+1,r);
	merge(p+l,p+mid+1,p+mid+1,p+r+1,t+l);
	copy(t+l,t+r+1,p+l);
}
void solve()
{
	cx[0]=cy[0]=0;
	for(int i=1;i<=n;i++)
		p[i].id=i,p[i].T=T[i];
	
	memset(f,127,sizeof(f));f[0]=0;
	sort(p+1,p+1+n,cmpT);DC(1,n);
	printf("%lld\n",f[n]);
}
int main()
{
	freopen("input","r",stdin);
	red(n),red(S);
	for(int i=1;i<=n;i++)
	{
		red(T[i]),red(F[i]);
		T[i]+=T[i-1],F[i]+=F[i-1];
	}
	for(int i=1;i<=n;i++)
	{
		cy[i]=(LL)(S-T[i-1])*(F[n]-F[i-1]);
		cx[i]=F[i-1];
	}
	solve();	
	return 0;
}

uva12538 Version Controlled IDE

发表于 2017-01-03 | 更新于 2018-06-18

Link

uva太慢了，还是再vjudge上看题目吧。。

FHQ Treap

学习了FHQ Treap的基本操作，以及可持久化Treap的写法。

`Merge(a,b)`

把a，b合并为一个Treap。前提是a中的所有元素都比b中的小，这样就可以按照可并堆的方法合并了。

`Split(pos,K)`

将treap分裂成两个，第一个包含了前K个元素，第二个包含剩下的元素。写法和平衡树的查找第K大有些类似。函数返回一个pair，具体实现比较容易脑补出来。

`Build(seq)`

把一个序列 $O(n)$ 构建成Treap。如果是其它的平衡树的话，插入一个序列一般是用递归建立一个完全二叉树。Treap并不能那么做，因为以节点的优先级来确保全局的平衡。于是Orz Sengxian。对于一个有序的序列，依次处理每个元素。维护一个栈，为每个元素新建一个节点，如果新的节点的优先级比栈顶元素小，就退栈，相应地连边。

Persistence

在Merge和Split中，对节点的所有修改都要在副本上进行。每次的花费空间期望应该是 $O(log\ n)$ 级别的。但是由于一次操作可能要多次Split和Merge，导致空间常数大了一些。。如果大神们有又好写又省空间的写法欢迎指教。。。

Code

//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
#define sred(x) scanf("%s",x+1)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXL=10000000+10,MAXN=50000+10,P=1e5+7;
using std::pair;
using std::make_pair;
struct TreapNode
{
	TreapNode *son[2];
	char c;int py,sz;
	TreapNode(){}
	TreapNode(int _py):py(_py){son[0]=son[1]=0;}
	void up(){sz=son[0]->sz+son[1]->sz+1;}
}*null=new TreapNode,*root[MAXN],*ME=new TreapNode[MAXL];
typedef pair<TreapNode*,TreapNode*> Np;
void InitTreap()
{
	null->py=P,null->sz=null->c=0;
	null->son[0]=null->son[1]=null;
}
TreapNode *newTreapNode(char c)
{
	static TreapNode *cur;
	cur=ME++;cur->c=c;cur->py=rand()%P;
	cur->son[0]=cur->son[1]=null;
	return cur;
}
TreapNode *newTreapNode(TreapNode *old)
{
	static TreapNode *cur;
	cur=ME++;*cur=*old;return cur;
}
TreapNode *Build(char *s)
{
	static TreapNode *stack[MAXN],*empty=new TreapNode(-P);
	static int top;stack[top=0]=empty;
	for(int i=1,endi=strlen(s+1);i<=endi;i++)
	{
		TreapNode *cur=newTreapNode(s[i]),*last=null;
		while(cur->py<stack[top]->py)
		{
			stack[top]->up();//其形态已经确定了
			last=stack[top--];
		}
		stack[top]->son[1]=cur;cur->son[0]=last;
		stack[++top]=cur;
	}
	while(top)
	{
		stack[top-1]->son[1]=stack[top];
		stack[top]->up();top--;
	}
	return empty->son[1];
}
TreapNode *Merge(TreapNode *a,TreapNode *b)
{
	if(a==null) return newTreapNode(b);
	if(b==null) return newTreapNode(a);
	TreapNode *cur;
	if(a->py<=b->py)
	{
		cur=newTreapNode(a);
		cur->son[1]=Merge(cur->son[1],b);
		cur->up();
	}
	else
	{
		cur=newTreapNode(b);
		cur->son[0]=Merge(a,cur->son[0]);
		cur->up();
	}
	return cur;
}
Np Split(TreapNode *&pos,int K)
{
	Np res=make_pair(null,null);
	if(pos==null) return res;
	pos=newTreapNode(pos);
	if(K<=pos->son[0]->sz)
	{
		res=Split(pos->son[0],K);
		pos->son[0]=res.second,pos->up();
		res.second=pos;
	}
	else
	{
		res=Split(pos->son[1],K-pos->son[0]->sz-1);
		pos->son[1]=res.first,pos->up();
		res.first=pos;
	}
	return res;
}
TreapNode *Insert(TreapNode *root,int p,char *s)
{
	TreapNode *nodes=Build(s);
	Np sp=Split(root,p);
	return Merge(Merge(sp.first,nodes),sp.second);
}
TreapNode *Delete(TreapNode *root,int p,int cnt)//从p开始的cnt个
{
	--p;
	Np sp1=Split(root,p),
	   sp2=Split(sp1.second,cnt);
	return Merge(sp1.first,sp2.second);
}
int d;
void out(TreapNode *pos)
{
	if(pos==null) return;
	out(pos->son[0]);
	putchar(pos->c);
	if(pos->c=='c') d--;	
	out(pos->son[1]);
}
void PutStr(TreapNode *root,int p,int cnt)
{
	--p;
	Np sp1=Split(root,p),
	   sp2=Split(sp1.second,cnt);
	out(sp2.first);puts("");
}
void print(TreapNode *root)
{
	puts("BEGIN");
	out(root);
	puts("\nEND");
}
int main()
{
	srand(0x1f1f1f1f);
	InitTreap();
	static char s[MAXN];
	int n,ver;red(n);
	root[ver=0]=null;
	for(int i=1;i<=n;i++)
	{
		int opt,v,p,c;red(opt);
		switch(opt)
		{
			case 1:red(p),sred(s);p+=d;
				   root[ver+1]=Insert(root[ver],p,s);
				   ver++;
				   break;
			case 2:red(p),red(c);p+=d,c+=d;
				   root[ver+1]=Delete(root[ver],p,c);
				   ver++;
				   break;
			case 3:red(v),red(p),red(c);v+=d,p+=d,c+=d;
				   PutStr(root[v],p,c);
				   break;
		}
		//print(root[ver]);
	}
	return 0;
}

Lucida

It's been a while.

222 日志

127 标签