数论分块入门 Libreoj 6277. 数列分块入门 1

 1 #include
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=5e4+5;
 5 int blg[N],L[N],R[N],tag[N],sum[N],a[N],block,tot;
 6 void split_block(int n)
 7 {
 8     block=sqrt(n);//每块有根号n个数 
 9     tot=n/block;//有多少块 
10     if(n%block)tot++;
11 
12     for(int i=1;i<=tot;i++)
13     {
14         L[i]=(i-1)*block+1;
15         R[i]=i*block;
16     }
17     R[tot]=n;
18     for(int i=1;i<=n;i++)
19     blg[i]=(i-1)/block+1;
20 }
21 void update(int l,int r,int val)
22 {
23     if(blg[l]==blg[r])
24     {
25         for(int i=l;i<=r;i++)
26         {
27             sum[blg[l]]+=val;
28             a[i]+=val;
29         }
30         return;
31     }
32     for(int i=l;i<=R[blg[l]];i++)
33     {
34         sum[blg[l]]+=val;
35         a[i]+=val;
36     }
37     for(int i=L[blg[r]];i<=r;i++)
38     {
39         sum[blg[r]]+=val;
40         a[i]+=val;
41     }
42     for(int i=blg[l]+1;i<=blg[r]-1;i++)
43     {
44         sum[i]+=block*val;
45         tag[i]+=val;
46     }
47 }
48 ll query(int l,int r)
49 {
50     ll ans=0;
51     if(blg[l]==blg[r])
52     {
53         for(int i=l;i<=r;i++)
54         ans+=a[i]+tag[blg[l]];
55         return ans;
56     }
57     for(int i=l;i<=R[blg[l]];i++)
58     ans+=a[i]+tag[blg[l]];
59     
60     for(int i=L[blg[r]];i<=r;i++)
61     ans+=a[i]+blg[r];
62     
63     for(int i=blg[l]+1;i<=blg[r]-1;i++)
64     ans+=sum[i];
65     return ans;
66 }
67 
68 int main()
69 {
70     int n,opt,l,r,k;
71     scanf("%d",&n);
72     split_block(n);
73     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
74     for(int i=1;i<=n;i++)
75     {
76         scanf("%d%d%d%d",&opt,&l,&r,&k);
77         if(opt) printf("%lld\n",query(r,r));
78         else update(l,r,k);
79     }
80     return 0;
81 }