本文主要是介绍A Simple Problem with Integers 上海大都会赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://www.nowcoder.com/acm/contest/163/H
两种操作 区间平方取模和区间求和 模数是2018 很蹊跷 感觉运算几次之后会变为0或1 就打了个表 发现了循环节长度大部分是6 少数是2和3 只有2017自己是1 为统一取个lcm=6即可 但是每个数不一定要运算几次才能进入循环节 有345不等 直接取个10
当一个区间内所有数都进入循环节后 则可以对这个区间直接更新或查询 否则继续向下二分 最后会落到叶节点身上 开个变量记录一下这个数被操作了几次 到十次就记为进入循环节
还有就是pushup和pushdown的设计比较麻烦 还需要考虑合并循环节和循环节的后移
感觉线段树的题目一般就是两类 一是抽象建模 这种题一般不好想 但是只要思路理清了 那几个函数都不用怎么改 二是这种刚正面的题 各种操作将你安排的明明白白..一般会有一些神奇的规律来剪枝之类
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;struct node
{int l;int r;int sum;int cnt;int laz;int flag;int val[6];int ptr;
};node tree[200010];
int pre[3000][20];
int ary[50010];
int n,q;void init()
{int i,j,val;for(i=0;i<2018;i++){val=i;for(j=0;j<16;j++){pre[i][j]=val;val=(val*val)%2018;}}
}void pushup(int cur)
{int i;tree[cur].sum=tree[2*cur].sum+tree[2*cur+1].sum;if(tree[2*cur].flag&&tree[2*cur+1].flag){tree[cur].ptr=0;for(i=0;i<6;i++){tree[cur].val[i]=tree[2*cur].val[(tree[2*cur].ptr+i)%6]+tree[2*cur+1].val[(tree[2*cur+1].ptr+i)%6];}tree[cur].flag=1;}
}void pushdown(int cur)
{int gou;if(tree[cur].laz!=0){gou=tree[cur].laz;tree[2*cur].ptr=(tree[2*cur].ptr+gou)%6;tree[2*cur].laz+=gou;tree[2*cur].sum=tree[2*cur].val[tree[2*cur].ptr];tree[2*cur+1].ptr=(tree[2*cur+1].ptr+gou)%6;tree[2*cur+1].laz+=gou;tree[2*cur+1].sum=tree[2*cur+1].val[tree[2*cur+1].ptr];tree[cur].laz=0;}
}void build(int l,int r,int cur)
{int m,i;tree[cur].l=l;tree[cur].r=r;tree[cur].sum=0;tree[cur].cnt=0;tree[cur].laz=0;tree[cur].flag=0;for(i=0;i<6;i++){tree[cur].val[i]=0;}tree[cur].ptr=0;if(l==r){tree[cur].sum=ary[l];for(i=0;i<6;i++){tree[cur].val[i]=pre[ary[l]][10+i];}return;}m=(l+r)/2;build(l,m,2*cur);build(m+1,r,2*cur+1);pushup(cur);
}void update(int pl,int pr,int cur)
{if(pl<=tree[cur].l&&tree[cur].r<=pr){if(tree[cur].flag){tree[cur].ptr=(tree[cur].ptr+1)%6;tree[cur].laz=(tree[cur].laz+1)%6;tree[cur].sum=tree[cur].val[tree[cur].ptr];return;}}if(tree[cur].l==tree[cur].r)//flag必为0{tree[cur].sum=(tree[cur].sum*tree[cur].sum)%2018;tree[cur].cnt++;if(tree[cur].cnt==10) tree[cur].flag=1;return;}pushdown(cur);if(pl<=tree[2*cur].r) update(pl,pr,2*cur);if(pr>=tree[2*cur+1].l) update(pl,pr,2*cur+1);pushup(cur);
}int query(int pl,int pr,int cur)
{int res;if(pl<=tree[cur].l&&tree[cur].r<=pr){return tree[cur].sum;}pushdown(cur);res=0;if(pl<=tree[2*cur].r) res+=query(pl,pr,2*cur);if(pr>=tree[2*cur+1].l) res+=query(pl,pr,2*cur+1);return res;
}int main()
{int t,cas,i,l,r;char op[10];init();scanf("%d",&t);for(cas=1;cas<=t;cas++){scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&ary[i]);}build(1,n,1);printf("Case #%d:\n",cas);scanf("%d",&q);while(q--){scanf("%s%d%d",op,&l,&r);if(op[0]=='C'){update(l,r,1);}else{printf("%d\n",query(l,r,1));}}}return 0;
}
这篇关于A Simple Problem with Integers 上海大都会赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
