Given  integers . There are 2 types of operations:

  • 1 l r: Change  to ;
  • 2 l r: Query the value of  modulo 99971.

For each query, please output the answer.

【题解】难得一眼秒…打个表发现48一循环,lazy tag永久标记一下,每次要查询的区间就是原来的区间+tag%48。

/********************************************

	Title		ZOJ4009.cpp
	Author 		TomatoLoveCoconut
	Time		2018-3-31
	History		Created 2018-3-31
	
	Version		1.0.0
	
	Tags:		SGT


	while(true) RP++;
	
		 QAQ

*********************************************/


#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define base 311
#define mod 19270817
#define maxlongint 2147483647
#define maxint 32767
#define pi (double)acos(-1.0)
#define eps 1e-
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
//SGT
#define MID ((l+r)>>1)
#define lson o<<1
#define rson o<<1|1
//clear the array
#define cla(a) memset(a,0,sizeof(a))
#define clb(a) memset(a,INF,sizeof(a));
#define clc(a) memset(a,-1,sizeof(a));
#define maxn 500010


using namespace std;


//complex
struct Complex{
    double x,y;
    Complex(double xx=0,double yy=0){x=xx,y=yy;}
};
inline Complex operator + (Complex a,Complex b){return Complex(a.x+b.x,a.y+b.y);}
inline Complex operator - (Complex a,Complex b){return Complex(a.x-b.x,a.y-b.y);}
inline Complex operator * (Complex a,Complex b){return Complex(a.x*b.x-a.y*b.y,a.y*b.x+b.y*a.x);}
//BIT
inline int lowbit(int x){return x&(-x);}




//var

int N=99971;
inline int qpow(int x,int n)
{
	if (n==1) return x;
	if (n==0) return 1;
	int ans=1;
	ans=qpow(x,n>>1)%N;
	ans=(ll)ans*ans%N;
	if (n&1) ans=(ll)ans*x%N;
	return ans%N;
}

struct Node{
	int lazy,sum[50];
}T[maxn];
int cur[50];
int a[maxn];
int n;


inline void build(int o,int l,int r)
{
	T[o].lazy=0;
	if (!o) return ;
	if (l>r) return ;
	if (l==r)
	{
		T[o].sum[0]=a[l];
		for (int i=1;i<48;i++)
			T[o].sum[i]=qpow(T[o].sum[i-1],3)%N;
		return ;
	}
	build(lson,l,MID);
	build(rson,MID+1,r);
	for (int i=0;i<48;i++)
		T[o].sum[i]=(T[lson].sum[i]+T[rson].sum[i])%N;
	return ;
}

inline void update(int o,int l,int r,int L,int R)
{
	if (L<=l && r<=R)
	{
		T[o].lazy++;
		T[o].lazy%=N;
		return ;
	}
	int mid=MID;
	if (L<=mid)
		update(lson,l,MID,L,R);
	if (R>mid)
		update(rson,MID+1,r,L,R);
	for (int i=0;i<48;i++)
		T[o].sum[i]=(T[lson].sum[(i+T[lson].lazy)%48]+T[rson].sum[(i+T[rson].lazy)%48])%N;
}

inline int query(int o,int l,int r,int L,int R,int del)
{
	del=(del+T[o].lazy)%48;
	if (L<=l && r<=R)
	{
		return (T[o].sum[del])%N;
	}
	int cur=0;
	int mid=MID;
	if (L<=mid)
		cur=(cur+query(lson,l,MID,L,R,del))%N;
	if (R>mid)
		cur=(cur+query(rson,MID+1,r,L,R,del))%N;
	return cur%N;
}


int main()
{
	int n,q;
	int T;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d%d",&n,&q);
		for (int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			a[i]%=N;
		}
		build(1,1,n);
		while (q--)
		{
			int opt,l,r;
			scanf("%d%d%d",&opt,&l,&r);
			if (opt==1)
				update(1,1,n,l,r);
			else printf("%d\n",query(1,1,n,l,r,0));
		}
	}
	return 0;
}
分类: 线段树

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注