RT,是在loj上的数列分块入门3。

暂时只有0分。

如能提供hack数据也可。

代码：

#include <bits/stdc++.h>
using namespace std;
long long a[100010], bel[100010], st[1010], en[1010], mark[1010], n, sq, opt, l, r, c;
vector<long long> v[1010];
void init() {
    for (int i = 1; i <= sq; i++) {
        st[i] = n / sq * (i - 1) + 1;
        en[i] = n / sq * i;
    }
    en[sq] = n;

    for (int i = 1; i <= sq; i++) {
        for (int j = st[i]; j <= en[i]; j++) {
            bel[j] = i;
            v[i].push_back(a[j]);
        }
    }

    for (int i = 1; i <= sq; i++) {
        sort(v[i].begin(), v[i].end());
    }
}
int main() {
    cin >> n;
    sq = sqrt(n);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    init();

    for (int i = 1; i <= n; i++) {
        cin >> opt >> l >> r >> c;

        if (opt == 0) {
        	if(bel[l] == bel[r])
        	{
        		for(int j = l;j <= r;j++)
        		{
        			a[j]+=c;
				}
				v[bel[l]].clear();
				for(int j = st[bel[l]];j <= en[bel[l]];j++)
				{
					v[bel[l]].push_back(/*i*/a[j]);
				}
				sort(v[bel[l]].begin(),v[bel[l]].end());
				continue;
			}
        	
            for (int j = l; j <= en[bel[l]]; j++) {
                a[j] += c;
            }

            for (int j = st[bel[r]]; j <= r; j++) {
                a[j] += c;
            }

            for (int j = bel[l] + 1; j <= bel[r] - 1; j++) {
                mark[j] += c;
            }

            v[bel[l]].clear();

            for (int j = st[bel[l]]; j <= en[bel[l]]; j++) {
                v[bel[l]].push_back(a[j]);
            }

            sort(v[bel[l]].begin(), v[bel[l]].end());
            
            v[bel[r]].clear();

            for (int j = st[bel[r]]; j <= en[bel[r]]; j++) {
                v[bel[r]].push_back(a[j]);
            }

            sort(v[bel[r]].begin(), v[bel[r]].end());
        }
        else
        {
        	if(bel[l] == bel[r])
        	{
        		long long mmax = -2147483647,flag = 0;
        		for(int j = l;j <= r;j++)
        		{
        			if(a[j]+mark[bel[l]] < c)
        			{
        				mmax = max(mmax,a[j]+mark[bel[l]]);
        				flag = 1;
					}
				}
				cout<<(flag?mmax:-1)<<endl;
				continue;
			}
        	long long mmax = -2147483647,flag = 0;
        	for(int j = l;j <= en[bel[l]];j++)
        	{
        		if(c-a[j]-mark[bel[j]] > 0)
        		{
        			mmax = max(mmax,a[j]+mark[bel[j]]);
        			flag = 1;
				}
			}
			for(int j = st[bel[r]];j <= r;j++)
			{
				if(c-a[j]-mark[bel[j]] > 0)
				{
					mmax = max(mmax,a[j]+mark[bel[j]]);
					flag = 1;
				}
			}
			for(int j = bel[l]+1;j <= bel[r]-1;j++)
			{
				//int x = v[j].lower_bound(v[j].begin(),v[j].end())
				long long x = 0,l = 0,r = v[j].size();
				if(v[j][0]+mark[j] >= c)
				{
					continue;
				}
				while(l <= r)
				{
					int mid = (l+r)/2;
					if(v[j][mid]+mark[j] < c)
					{
						x = l;
						l = mid+1;
					}
					else
					{
						r = mid-1;
					}
				}
				flag = 1;
				mmax = max(mmax,v[j][x]+mark[j]);
			}
			cout<<(flag?mmax:-1)<<endl;
		}
    }
}