[java线段树]2015上海邀请赛 D Doom
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[java线段树]2015上海邀请赛 D Doom，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2819字，纯文字阅读大概需要5分钟。
内容图文
题意：n个数 m个询问
每个询问[l, r]的和， 再把[l, r]之间所有的数变为平方(模为9223372034707292160LL)
很明显的线段树
看到这个模(LLONG_MAX为9223372036854775807) 很明显平方时会爆LL
很容易发现所有数平方模了几次之后值就不再改变了 而且这个“几次”相当小 因此直接暴力搞就好了
public
static
void
main(String[] args)
{
Scanner in = new Scanner(System.in);
BigInteger a=BigInteger.valueOf(2); // 这里看的是2的平方
Long b=9223372034707292160L;
BigInteger mod=new BigInteger(b.toString());
for(int i=1;i<=40;i++)
{
a=a.multiply(a).mod(mod);
System.out.println(i + ":" + a); // 平方i次之后的值 }
}
1
import java.io.*;
2import java.util.*;
3import java.math.*;
4import java.nio.charset.StandardCharsets;
5 6publicclass Main
7{
8static BigInteger li=BigInteger.ZERO;
9static Long b=9223372034707292160L;
10static BigInteger mod=new BigInteger(b.toString());
11static BigInteger[] sum=new BigInteger[200005];
12staticboolean[] num=newboolean[200005];
13static InputReader in = new InputReader();
14publicstaticvoid pushup(int rt)
15 {
16 sum[rt]=(sum[rt*2].add(sum[rt*2+1])).mod(mod);
17 num[rt]=num[rt*2]&num[rt*2+1];
18 }
19publicstaticvoid build(int l, int r, int rt)
20 {
21if(l==r)
22 {
23 sum[rt]=in.nextBigInteger();
24 num[rt]=false;
25return ;
26 }
27int m=(l+r)/2;
28 build(l, m, rt*2);
29 build(m+1, r, rt*2+1);
30 pushup(rt);
31 }
32publicstatic BigInteger query(int L, int R, int l, int r, int rt)
33 {
34if(L<=l && r<=R)
35return sum[rt];
36int m=(l+r)/2;
37 BigInteger ret=li;
38if(L<=m)
39 ret=ret.add(query(L, R, l, m, rt*2)).mod(mod);
40if(R>m)
41 ret=ret.add(query(L, R, m+1, r, rt*2+1)).mod(mod);
42return ret.mod(mod);
43 }
44publicstaticvoid update(int p, int l, int r, int rt)
45 {
46if(l==r)
47 {
48 BigInteger cur=(sum[rt].multiply(sum[rt])).mod(mod);
49if(sum[rt].equals(cur))
50 num[rt]=true;
51 sum[rt]=cur;
52return ;
53 }
54int m=(l+r)/2;
55if(p<=m)
56 update(p, l, m, rt*2);
57else 58 update(p, m+1, r, rt*2+1);
59 pushup(rt);
60 }
61staticint n;
62publicstaticvoid update(int L, int R, int l, int r, int rt)
63 {
64if(L<=l && r<=R)
65 {
66if(num[rt])
67return ;
68if(l==r)
69 update(l, 1, n, 1);
70else 71 {
72int mm=(l+r)/2;
73 update(L, R, l, mm, rt<<1);
74 update(L, R, mm+1, r, rt<<1|1);
75 }
76 77return ;
78 }
79int m=(l+r)/2;
80if(L<=m)
81 update(L, R, l, m, rt*2);
82if(R>m)
83 update(L, R, m+1, r, rt*2+1);
84 pushup(rt);
85 }
86publicstaticvoid main(String[] args)
87 {
88int t, ca=1;
89 t=in.nextInt();
90while((t--)!=0)
91 {
92 n=in.nextInt();
93int m=in.nextInt();
94 build(1, n, 1);
95 System.out.println("Case #" + ca + ":");
96 ca++;
97 BigInteger ans=li;
98while((m--)!=0)
99 {
100int l, r;
101 l=in.nextInt();
102 r=in.nextInt();
103 ans=ans.add(query(l, r, 1, n, 1)).mod(mod);
104 System.out.println(ans);
105 update(l, r, 1, n, 1);
106 }
107 }
108 }
109 }
原文：http://www.cnblogs.com/Empress/p/4529506.html
内容总结
以上是互联网集市为您收集整理的[java线段树]2015上海邀请赛 D Doom全部内容，希望文章能够帮你解决[java线段树]2015上海邀请赛 D Doom所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。