UOJ46 清华集训2014玄学（线段树）

　　注意到操作有结合律，容易想到用一个矩形表示第i次操作对第j个位置的数的影响。那么修改是单行内的区间修改，而查询是单列内的区间查询。这样二维线段树上以列为外层行为内层直接打标记就可以维护。然后就喜闻乐见的被卡常了。当年的标算似乎就是树套树，然而都是可持久化AVL树之类难懂的话。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define N 100010

#define mp(x,y) make_pair((x),(y))

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

typedef pair<int,int> pii;

int n,m,q,t,a[N],root[N<<2],lastans,isonline,cnt;

pii o;

struct data{int l,r;pii x,y;

}tree[N<<8];

pii trans(pii a,pii b){a.first=1ll*a.first*b.first%m;a.second=1ll*a.second*b.first%m;a.second=(a.second+b.second)%m;return a;}

void up(int k){tree[k].x=trans(tree[tree[k].l].x,tree[tree[k].r].x);}

int newnode(){int k=++cnt;tree[k].x=tree[k].y=o;return k;}

void update(int &k,pii p)

{

	if (!k) k=newnode();

	tree[k].x=trans(tree[k].x,p);

	tree[k].y=trans(tree[k].y,p);

}

void down(int k)

{

	update(tree[k].l,tree[k].y);

	update(tree[k].r,tree[k].y);

	tree[k].y=o;

}

void mul(int &k,int l,int r,int x,int y,pii p)

{

	if (!k) k=newnode();

	if (l==x&&r==y)

	{

		update(k,p);

		return;

	}

	if (tree[k].y!=o) down(k);

	int mid=l+r>>1;

	if (y<=mid) mul(tree[k].l,l,mid,x,y,p);

	else if (x>mid) mul(tree[k].r,mid+1,r,x,y,p);

	else mul(tree[k].l,l,mid,x,mid,p),mul(tree[k].r,mid+1,r,mid+1,y,p);

	up(k);

}

void modify(int k,int l,int r,int x,int p,int q,pii y)

{

	mul(root[k],1,n,p,q,y);

	if (l==r) return;

	int mid=l+r>>1;

	if (x<=mid) modify(k<<1,l,mid,x,p,q,y);

	else modify(k<<1|1,mid+1,r,x,p,q,y);

}

pii Q(int &k,int l,int r,int x)

{

	if (!k) return o;

	if (l==r) return tree[k].x;

	if (tree[k].y!=o) down(k);

	int mid=l+r>>1;

	if (x<=mid) return Q(tree[k].l,l,mid,x);

	else return Q(tree[k].r,mid+1,r,x);

}

pii query(int k,int l,int r,int x,int y,int p)

{

	if (l==x&&r==y) return Q(root[k],1,n,p);

	int mid=l+r>>1;

	if (y<=mid) return query(k<<1,l,mid,x,y,p);

	else if (x>mid) return query(k<<1|1,mid+1,r,x,y,p);

	else return trans(query(k<<1,l,mid,x,mid,p),query(k<<1|1,mid+1,r,mid+1,y,p));

}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("ex_input3.txt","r",stdin);

	freopen("a.out","w",stdout);

	const char LL[]="%I64d\n";

#else

	const char LL[]="%lld\n";

#endif

	if (read()&1) isonline=1;o.first=1;tree[0].x=o;

	n=read(),m=read();

	for (int i=1;i<=n;i++) a[i]=read();

	q=read();

	while (q--)

	{

		int op=read();

		if (op==1)

		{

			int l=read(),r=read(),a=read(),b=read();

			if (isonline) l^=lastans,r^=lastans;

			t++;modify(1,1,100000,t,l,r,mp(a,b));

		}

		else

		{

			int l=read(),r=read(),x=read();

			if (isonline) l^=lastans,r^=lastans,x^=lastans;

			pii u=query(1,1,100000,l,r,x);

			printf("%d\n",lastans=(1ll*a[x]*u.first+u.second)%m);

		}

	}

	return 0;

}

　　考虑小常数做法。注意到x次修改至多会将序列划分成2x+1个不同的段，那么用线段树对修改进行维护，节点内记录这些修改将序列划分成的段，显然总段数是O(nlogn)的（nq同阶）。然而无法在每次修改时都对所有影响到的节点进行修改，因为单个节点修改并非O(1)或O(log)。不过可以在一个节点的修改全部出现后，通过归并排序两个子节点来得到该节点信息。于是这样修改总复杂度就是O(nlogn)。查询时在线段树上区间查询再在节点上二分即可。同样是两个log但常数显然小了很多。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define N 100010

#define mp(x,y) make_pair((x),(y))

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

typedef pair<int,int> pii;

int n,m,q,t,a[N],lastans,isonline,L[N<<2],R[N<<2];

pii o;

pii trans(pii a,pii b){a.first=1ll*a.first*b.first%m;a.second=1ll*a.second*b.first%m;a.second=(1ll*a.second+b.second)%m;return a;}

struct seg{int l,r;pii x;};

vector<seg> tree[N<<2];

vector<int> id[N];

void build(int k,int l,int r)

{

	id[r].push_back(k);L[k]=l,R[k]=r;

	tree[k].push_back((seg){1,n,o});

	if (l==r) return;

	int mid=l+r>>1;

	build(k<<1,l,mid),build(k<<1|1,mid+1,r);

}

vector<seg> merge(vector<seg> a,vector<seg> b)

{

	vector<seg> c;

	for (int i=0,j=0;i<a.size()||j<b.size();)

	if (a[i].r==b[j].r) c.push_back((seg){max(a[i].l,b[j].l),a[i].r,trans(a[i].x,b[j].x)}),i++,j++;

	else if (a[i].r<b[j].r) c.push_back((seg){max(a[i].l,b[j].l),a[i].r,trans(a[i].x,b[j].x)}),i++;

	else c.push_back((seg){max(a[i].l,b[j].l),b[j].r,trans(a[i].x,b[j].x)}),j++;

	return c;

}

pii query(int k,int l,int r,int x)

{

	if (L[k]==l&&R[k]==r)

	{

		int l=0,r=tree[k].size(),p=0;

		while (l<=r)

		{

			int mid=l+r>>1;

			if (x<=tree[k][mid].r) p=mid,r=mid-1;

			else l=mid+1;

		}

		return tree[k][p].x;

	}

	int mid=L[k]+R[k]>>1;

	if (r<=mid) return query(k<<1,l,r,x);

	else if (l>mid) return query(k<<1|1,l,r,x);

	else return trans(query(k<<1,l,mid,x),query(k<<1|1,mid+1,r,x));

}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("b.out","w",stdout);

	const char LL[]="%I64d\n";

#else

	const char LL[]="%lld\n";

#endif

	if (read()&1) isonline=1;o.first=1;

	n=read(),m=read();

	for (int i=1;i<=n;i++) a[i]=read();

	q=read();build(1,1,100000);for (int i=1;i<=100000;i++) reverse(id[i].begin(),id[i].end());

	while (q--)

	{

		int op=read();

		if (op==1)

		{

			int l=read(),r=read(),a=read(),b=read();vector<seg>tmp;

			if (isonline) l^=lastans,r^=lastans;

			if (l>1) tmp.push_back((seg){1,l-1,o});

			tmp.push_back((seg){l,r,mp(a,b)});

			if (r<n) tmp.push_back((seg){r+1,n,o});

			t++;

			for (int k:id[t])

			if (L[k]==R[k]) tree[k]=merge(tree[k],tmp);

			else tree[k]=merge(tree[k<<1],tree[k<<1|1]);

		}

		else

		{

			int l=read(),r=read(),x=read();

			if (isonline) l^=lastans,r^=lastans,x^=lastans;

			pii u=query(1,l,r,x);

			printf("%d\n",lastans=(1ll*a[x]*u.first+u.second)%m);

		}

	}

	return 0;

}

巴特西

UOJ46 清华集训2014玄学（线段树）

最新文章

热门文章