题目：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
       
        >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
        
         >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<
         
          >q[x].ch;q[x].a=read();change(1,1,n,x);}    }  return 0;}