Libreoj 6279. 数列分块入门 3

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