[java线段树]2015上海邀请赛 D Doom

浏览数：24 / 时间：2015年06月08日

题意：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.*;
  2 import java.util.*;
  3 import java.math.*;
  4 import java.nio.charset.StandardCharsets;
  5 
  6 public class Main
  7 {
  8     static BigInteger li=BigInteger.ZERO;
  9     static Long b=9223372034707292160L;
 10     static BigInteger mod=new BigInteger(b.toString());
 11     static BigInteger[] sum=new BigInteger[200005];
 12     static boolean[] num=new boolean[200005];
 13     static InputReader in = new InputReader();
 14     public static void 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     }
 19     public static void build(int l, int r, int rt)
 20     {
 21         if(l==r)
 22         {
 23             sum[rt]=in.nextBigInteger();
 24             num[rt]=false;
 25             return ;
 26         }
 27         int m=(l+r)/2;
 28         build(l, m, rt*2);
 29         build(m+1, r, rt*2+1);
 30         pushup(rt);
 31     }
 32     public static BigInteger query(int L, int R, int l, int r, int rt)
 33     {
 34         if(L<=l && r<=R)
 35             return sum[rt];
 36         int m=(l+r)/2;
 37         BigInteger ret=li;
 38         if(L<=m)
 39             ret=ret.add(query(L, R, l, m, rt*2)).mod(mod);
 40         if(R>m)
 41             ret=ret.add(query(L, R, m+1, r, rt*2+1)).mod(mod);
 42         return ret.mod(mod);
 43     }
 44     public static void update(int p, int l, int r, int rt)
 45     {
 46         if(l==r)
 47         {
 48             BigInteger cur=(sum[rt].multiply(sum[rt])).mod(mod);
 49             if(sum[rt].equals(cur))
 50                 num[rt]=true;
 51             sum[rt]=cur;
 52             return ;
 53         }
 54         int m=(l+r)/2;
 55         if(p<=m)
 56             update(p, l, m, rt*2);
 57         else 
 58             update(p, m+1, r, rt*2+1);
 59         pushup(rt);
 60     }
 61     static int n;
 62     public static void update(int L, int R, int l, int r, int rt)
 63     {
 64         if(L<=l && r<=R)
 65         {
 66             if(num[rt])
 67                 return ;
 68             if(l==r)
 69                 update(l, 1, n, 1);
 70             else 
 71             {
 72                 int mm=(l+r)/2;
 73                 update(L, R, l, mm, rt<<1);
 74                 update(L, R, mm+1, r, rt<<1|1);
 75             }
 76             
 77             return ;
 78         }
 79         int m=(l+r)/2;
 80         if(L<=m)
 81             update(L, R, l, m, rt*2);
 82         if(R>m)
 83             update(L, R, m+1, r, rt*2+1);
 84         pushup(rt);
 85     }
 86     public static void main(String[] args)
 87     {
 88         int t, ca=1;
 89         t=in.nextInt();
 90         while((t--)!=0)
 91         {
 92             n=in.nextInt();
 93             int m=in.nextInt();
 94             build(1, n, 1);
 95             System.out.println("Case #" + ca + ":");
 96             ca++;
 97             BigInteger ans=li;
 98             while((m--)!=0)
 99             {
100                 int 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 }