201912CSPT5魔数

题意：有一个从$1$到$n$的连续序列，有$q$次查询,对区间操作$[l,r]$：
$1.输出s=f(A_l)+f(A_{l+1})+...+f(A_r),f(x)=(x$%$2009731336725594113)$%$2019$
$2.t=s$
$3.A_l,A_{l+1},A_r$乘上$U_t$
$U[0-4]=314882150829468584,427197303358170108,1022292690726729920,1698479428772363217,2006101093849356424$

#include<bits/stdc++.h>
typedef unsigned long long ull;
using namespace std;
ull U[5]= 
{314882150829468584,427197303358170108,1022292690726729920,1698479428772363217,2006101093849356424
};
ull mod=2009731336725594113;
unordered_map<ull, int> mp;//mp[乘数]=编号 
ull f[35],a[1000010][35];//f[编号]=乘数,a[i][j]保存的是序列A乘以j后再经过f(x)运算后的结果 
int g[35][35];//转移方程，g[i][j]=k表示序号为i,j的两个数相乘结果会转移成序号为k的数 
int n,q;
ull mul(ull a, ull b)
{ull res=0;for(;b;b>>=1){if(b&1)res=(res+a)%mod;a=(a+a)%mod;}return res;
}
void getConvert()
{queue<ull> q;int id=1;for(int i=0;i<5;i++){q.push(U[i]);mp[U[i]]=id++;}while(q.size()){ull x=q.front();q.pop();f[mp[x]]=x;for(int i=0;i<5;i++){ull t=mul(x,U[i]);if(mp[t])continue;   mp[t]=id++;q.push(t);}}
//	for(int i=1;i<=50;i++)cout<<f[i]<<endl;for(int i=1;i<=32;i++)for(int j=i;j<=32;j++)g[i][j]=g[j][i]=mp[mul(f[i],f[j])];
}
int temp[1001];
struct Node
{int l,r;int sum=0;//区间和int tag;//标记当前区间被乘了哪一个数int s[33];//保存的是该区间乘以f[i]之后的结果//我们大可以把s[]看做是res的一个预测值，因为当前区间只会被乘32个数中的某一个,//res也就只会转变为这32个s[i]的某一个void trans(int now){for(int i=1;i<=32;i++)temp[i]=s[g[i][now]];for(int i=1;i<=32;i++)s[i]=temp[i];sum=s[28];//f[28]=1,所以s[28]就是A序列自身 //cout<<sum<<" "<<now<<" "<<tag<<endl;if(tag==0)tag=now;else tag=g[tag][now];}
}t[4000010];
void build(ull p,ull l,ull r)
{t[p].l=l;t[p].r=r;if(l==r){for(int i=1;i<=32;i++)t[p].s[i]=a[l][i]%2019;t[p].sum=t[p].s[28];t[p].tag=0;return ;}int mid=(l+r)>>1;build(p*2,l,mid);build(p*2+1,mid+1,r);for(int i=1;i<=32;i++)t[p].s[i]=t[p*2].s[i]+t[p*2+1].s[i];t[p].sum=t[p].s[28];t[p].tag=0;
}
void spread(int p)
{if(t[p].tag){t[p*2].trans(t[p].tag);t[p*2+1].trans(t[p].tag);t[p].tag=0;}
}
ull ask(ull p,ull l,ull r)
{if(t[p].r<l||t[p].l>r)return 0;if(t[p].l>=l&&t[p].r<=r)return t[p].sum;	spread(p);	ull val=0;int mid=(t[p].l+t[p].r)>>1;if(l<=mid)val+=ask(p*2,l,r);if(mid<r)val+=ask(p*2+1,l,r);return val;
}
void Mul(ull p,ull l,ull r,ull k)
{if(t[p].r<l||t[p].l>r)return ;if(t[p].l>=l&&t[p].r<=r){t[p].trans(k);return ;}spread(p);int mid=(t[p].l+t[p].r)>>1;if(l<=mid)Mul(p*2,l,r,k);if(mid<r)Mul(p*2+1,l,r,k);for(int i=1;i<=32;i++)t[p].s[i]=t[p*2].s[i]+t[p*2+1].s[i];t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
int main()
{getConvert();cin>>n>>q;for(int i=1;i<=n;i++)for(int j=1;j<=32;j++){if(i==1)a[i][j]=f[j]%mod;//因为序列是连续的,所以可以使用加法递推 else a[i][j]=(f[j]+a[i-1][j])%mod;//	cout<<a[i][j]<<" ";}build(1,1,n);for(int i=1;i<=q;i++){ull L,R;cin>>L>>R;ull ans=ask(1,L,R);cout<<ans<<endl;Mul(1,L,R,(ans%5)+1);//注意+1 }return 0;
}