【LOJ#573】【LNR#2】单枪匹马（线段树）

题面

题解

考虑拿线段树维护这个值，现在的问题就是左右怎么合并，那么就假设最右侧进来的那个分数是\(\frac{x}{y}\)的形式，那么就可以维护一下每一个值的系数，就可以直接合并了。

我代码又臭又长，还写得贼复杂

#include<iostream>

#include<cstdio>

using namespace std;

#define MOD 998244353

#define MAX 1000500

#define lson (now<<1)

#define rson (now<<1|1)

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,m,type,a[MAX],N,MX;

struct Num{int a,b,c;};

Num operator+(Num a,Num b){return (Num){(a.a+b.a)%MOD,(a.b+b.b)%MOD,(a.c+b.c)%MOD};}

Num operator*(Num a,int b){return (Num){1ll*a.a*b%MOD,1ll*a.b*b%MOD,1ll*a.c*b%MOD};}

struct Fact{Num a,b;};

Fact operator+(Fact a,int b){return (Fact){a.b*b+a.a,a.b};}

Fact Rev(Fact a){return (Fact){a.b,a.a};}

Fact Value(Fact a,int x,int y)

{

	int u=(1ll*a.a.a*x+1ll*a.a.b*y+a.a.c)%MOD;

	int v=(1ll*a.b.a*x+1ll*a.b.b*y+a.b.c)%MOD;

	return (Fact){(Num){0,0,u},(Num){0,0,v}};

}

struct Node{Fact s,v;}t[MAX<<2];

Node Calc(Node l,Node r)

{

	Node ret;swap(r.v.a,r.v.b);swap(r.s.a,r.s.b);

	ret.s=Value(l.v,r.s.a.c,r.s.b.c);

	Num a=(Num){(1ll*l.v.a.a*r.v.a.a+1ll*l.v.a.b*r.v.b.a)%MOD,(1ll*l.v.a.a*r.v.a.b+1ll*l.v.a.b*r.v.b.b)%MOD,(1ll*l.v.a.a*r.v.a.c+1ll*l.v.a.b*r.v.b.c+l.v.a.c)%MOD};

	Num b=(Num){(1ll*l.v.b.a*r.v.a.a+1ll*l.v.b.b*r.v.b.a)%MOD,(1ll*l.v.b.a*r.v.a.b+1ll*l.v.b.b*r.v.b.b)%MOD,(1ll*l.v.b.a*r.v.a.c+1ll*l.v.b.b*r.v.b.c+l.v.b.c)%MOD};

	ret.v=(Fact){a,b};

	return ret;

}

void Modify(int now,int l,int r,int p)

{

	if(l==r)

	{

		t[now].s=(Fact){(Num){0,0,a[l]},(Num){0,0,1}};

		t[now].v=(Fact){(Num){1,0,0},(Num){0,1,0}}+a[l];

		return;

	}

	int mid=(l+r)>>1;

	if(p<=mid)Modify(lson,l,mid,p);

	else Modify(rson,mid+1,r,p);

	t[now]=Calc(t[lson],t[rson]);

}

Node Query(int now,int l,int r,int L,int R)

{

	if(L==l&&r==R)return t[now];

	int mid=(l+r)>>1;

	if(R<=mid)return Query(lson,l,mid,L,R);

	if(L>mid)return Query(rson,mid+1,r,L,R);

	return Calc(Query(lson,l,mid,L,mid),Query(rson,mid+1,r,mid+1,R));

}

int main()

{

	n=read();m=read();type=read();N=n+m;MX=n;

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

	for(int i=1,lans=0;i<=m;++i)

	{

		int opt=read();

		if(opt==1)

		{

			int x=read();if(type==1)x^=lans;

			a[++MX]=x;Modify(1,1,N,MX);

		}

		else

		{

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

			if(type==1)l^=lans,r^=lans;

			Node u=Query(1,1,N,l,r);

			printf("%d %d\n",u.s.a.c,u.s.b.c);

			lans=u.s.a.c^u.s.b.c;

		}

	}

	return 0;

}

巴特西

【LOJ#573】【LNR#2】单枪匹马（线段树）

【LOJ#573】【LNR#2】单枪匹马（线段树）

题面

题解

最新文章

热门文章