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

╰半夏微凉° 2021-12-05 02:37 188阅读 0赞

注意到操作有结合律，容易想到用一个矩形表示第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;
    }

转载于:https://www.cnblogs.com/Gloid/p/11001107.html