暑假集训8.7数据结构专题-很妙的线段树( 觉醒力量（hidpower）)

题目：oj1710

因为存在修改和查询的操作，所以学长说可以很“轻易”的想到线段树....，装作我轻易的想到了，最后是要输出答案mod17及mod46189的结果，（关键点1）然后我们发现46189=11*13*17*19；于是我们想到但处理出答案mod每个质因数的答案，再利用中国剩余定理求出答案。（关键点2）考虑对枚举进入某各区间运算的数为1-p[i],因为p[i]很小所以可以处理。然后修改操作也变成log的。非常可写。

关于中国剩余定理：x=(∑ai*ti*mi)modM。ti是逆元。

上代码：

#include
#define il inline
#define LL long long
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
string s[17]={"Fight","Flying","Poison","Ground","Rock","Bug","Ghost","Steel","Fire","Water","Grass","Electric","Psychic","Ice","Dragon","Dark","Fairy"};
const int N=1e5+5;int n,m,p[5]={0,11,13,17,19},k[5],P=46189;
struct node{char ch;int a;}q[N];struct data{int b[5][20];}t[N<<2];
int read(){int x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=x*10+ch-48;return f*x;}
int ksm(int x,int y,int p){int b=x,ans=1;while(y){if(y&1)ans=ans*b%p;b=b*b%p;y>>=1;}return ans;}
LL ksml(LL x,LL y,int p){LL b=x,ans=1;while(y){if(y&1)ans=ans*b%p;b=b*b%p;y>>=1;}return ans;}
il void update(int x){for(int i=1;i<=4;i++)for(int j=0;j)t[x].b[i][j]=t[x<<1|1].b[i][t[x<<1].b[i][j]%p[i]];
}
void build(int x,int l,int r){if(l==r){for(int i=1;i<=4;i++){for(int j=0;j){if(q[l].ch=='+')t[x].b[i][j]=(j+q[l].a%p[i])%p[i];if(q[l].ch=='-')t[x].b[i][j]=(j-q[l].a%p[i]+p[i])%p[i];if(q[l].ch=='*')t[x].b[i][j]=q[l].a%p[i]*j%p[i];if(q[l].ch=='^')t[x].b[i][j]=ksm(j,q[l].a,p[i])%p[i];}}return;}int mid=(l+r)>>1;build(x<<1,l,mid);build(x<<1|1,mid+1,r);update(x);
}
void change(int x,int l,int r,int pos){if(l==r){for(int i=1;i<=4;i++)for(int j=0;j){if(q[l].ch=='+')t[x].b[i][j]=(j+q[l].a%p[i])%p[i];if(q[l].ch=='-')t[x].b[i][j]=(j-q[l].a%p[i]+p[i])%p[i];if(q[l].ch=='*')t[x].b[i][j]=q[l].a%p[i]*j%p[i];if(q[l].ch=='^')t[x].b[i][j]=ksm(j,q[l].a,p[i]);}return;}int mid=(l+r)>>1;if(pos<=mid)change(x<<1,l,mid,pos);else change(x<<1|1,mid+1,r,pos);update(x);
}
int main()
{n=read();m=read();for(int i=1;i<=n;i++){cin>>q[i].ch;q[i].a=read();}build(1,1,n);for(int i=1;i<=4;i++)k[i]=ksml((LL)(P/p[i]),(LL)(p[i]-2),p[i]);for(int i=1;i<=m;i++){int op=read();int x,y;if(op==1){x=read();cout<1].b[3][x%17]%17];LL ans=0;for(int i=1;i<=4;i++){ans=(ans+(LL)t[1].b[i][x%p[i]]*(LL)k[i]%P*(LL)(P/p[i])%P)%P;}printf(" %d\n",ans);}else{x=read();cin>>q[x].ch;q[x].a=read();change(1,1,n,x);}}return 0;
}

转载于:https://www.cnblogs.com/Jessie-/p/9440110.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！