网站计算机速成培训班,品牌注册名词解释,域名官网,网站建设分析从哪几个方面这道题真的是好题#xff0c;让我对线段树有了全新的认识#xff0c;至少让我真正感受到了线段树的神奇。 题意是就是线段树区间更新#xff0c;单点询问的问题#xff0c;不过这个题好就好在它的区间更新的点并不连续#xff01; adding c to each of Ai which satisfies…这道题真的是好题让我对线段树有了全新的认识至少让我真正感受到了线段树的神奇。 题意是就是线段树区间更新单点询问的问题不过这个题好就好在它的区间更新的点并不连续 adding c to each of Ai which satisfies a i b and (i - a) % k 0. 关键在于更新的点所满足的条件 1.在区间[a,b]中。 2.关于k的余数与a%k相等。 其中第二个条件保证了更新的点不连续但如果传统的先判断再更新则线段树失去了优势因为始终会超时。 本题突破口在于K的大小1 k 10结合第二个条件我们可以想到在线段树的 Lazy标记上做文章。 当k1 余数有 0 当k2 余数有 01 当k3 余数有 012 。。。。。 可以看到只有55种情况那么我们只需要将线段树的 Lazy标记 扩充为大小55的数组 然后根据相应的余数情况进行更新与查询即可。 1 #includeiostream2 #includesstream3 #includestack4 #includecstdio5 #includecstdlib6 #includecstring7 #includeclimits8 #includecctype9 #includequeue10 #includealgorithm11 #includecmath12 #includemap13 #includeset14 #define lson root1,l,mid15 #define rson root1|1,mid1,r16 17 #define inf 0x3f3f3f3f18 #define N 5001019 #define maxn 1000100020 #define mod 100000000721 using namespace std;22 23 int a[N];24 int b[11][11]; //用于将55种余数情况一 一 对 应25 struct NODE{26 int l,r;27 int v;28 int b[55];29 int mid(){30 return (lr)1;31 }32 }node[N2];33 34 void build(int root,int l,int r)35 {36 node[root].ll;37 node[root].rr;38 node[root].v0;39 memset(node[root].b,0,sizeof(node[root].b));40 if(lr) return;41 int midnode[root].mid();42 build(lson);43 build(rson);44 }45 46 void pushdown(int root) //关于pushdown函数个人觉得只需要询问时调用就行了而且也过了应该没问题有的话请指出谢谢47 {48 for(int i1; i10; i)49 {50 for(int j0; ji; j)51 {52 node[root1].b[b[i][j]]node[root].b[b[i][j]];53 node[root1|1].b[b[i][j]]node[root].b[b[i][j]];54 }55 }56 memset(node[root].b,0,sizeof(node[root].b));57 }58 59 void update(int x,int y,int root,int v,int k,int rd)60 {61 if(node[root].lxnode[root].ry)62 {63 node[root].b[b[k][rd]]v;64 node[root].vv;65 return;66 }67 int midnode[root].mid();68 if(ymid) update(x,y,root1,v,k,rd);69 else if(xmid) update(x,y,root1|1,v,k,rd);70 else71 {72 update(x,mid,root1,v,k,rd);73 update(mid1,y,root1|1,v,k,rd);74 }75 }76 77 int query(int root,int x)78 {79 if(node[root].lxnode[root].rx)80 {81 int ans0;82 for(int i1; i10; i)83 ansnode[root].b[b[i][x%i]];84 return ans;85 }86 pushdown(root);87 int midnode[root].mid();88 if(xmid) return query(root1,x);89 else return query(root1|1,x);90 }91 92 int main()93 {94 // freopen(lxx.txt,r,stdin);95 int group,figure,i,j,x,y,k,v,num;96 int cnt0;97 for(i1; i11; i)98 for(j0; ji; j)99 b[i][j]cnt;
100 while(~scanf(%d,group))
101 {
102 build(1,1,group);
103 memset(a,0,sizeof(a));
104 for(i1; igroup; i) scanf(%d,a[i]);
105 scanf(%d,group);
106 while(group--)
107 {
108 scanf(%d,num);
109 if(num1)
110 {
111 scanf(%d%d%d%d,x,y,k,v);
112 update(x,y,1,v,k,x%k);
113 }
114 else
115 {
116 scanf(%d,figure);
117 printf(%d\n,query(1,figure)a[figure]);
118 }
119 }
120 }
121 return 0;
122 } 不过感觉自己的代码风格还不够成熟继续努力 转载于:https://www.cnblogs.com/Kurokey/p/5222307.html
