100 pts NOIP T4

容易想到可以分治。但纯分治 $O(q n^2 \log n)$，只能得 $15pts$。

发现有区间 $max$，套上 ST 表。时间复杂度 $O(qn \log n)$，得到 $76pts$。

// 76 pts
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = -0x3f3f3f3f3f3f3f3f;
inline int read(){
	int k = 0,f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		k = k * 10 + c - '0';
		c = getchar();
	}
	return k * f;
}
inline void write(unsigned int x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x < 10) putchar(x + '0');
	else{
		write(x / 10);
		putchar(x % 10 + '0');
	}
}
int n,a[50005],pre[50005],ans[50005],ql,qr;
struct ST{
    int maxx[25][50005],st[50005];
    inline void init(){
        st[1] = 0;
        for(int i = 2;i <= n;i++) st[i] = st[i / 2] + 1;
        for(int j = 1,k = 1;j <= st[n];j++){
            for(int i = 1;i + (1 << j) - 1 <= n;i++) maxx[j][i] = max(maxx[j - 1][i],maxx[j - 1][i + k]);
            k <<= 1;
        }
    }
    inline int query(int l,int r){
        int len = r - l + 1;
        return max(maxx[st[len]][l],maxx[st[len]][r - (1 << st[len]) + 1]);
    }
}st1,st2;
inline void solve(int l,int r){
    if(l == r){
        if(ql <= 1 && qr >= 1) ans[l] = max(ans[l],a[l]);
        return;
    }
    int mid = (l + r) >> 1;
    solve(l,mid);
    solve(mid + 1,r);
    int maxx = INF;
    for(int i = l;i <= mid;i++){
        int tl = max(mid + 1,i + ql - 1),tr = min(n,i + qr - 1);
        if(tl <= tr) maxx = max(maxx,-pre[i - 1] + st1.query(tl,tr));
        if(maxx != INF) ans[i] = max(ans[i],maxx);
    }
    maxx = INF;
    for(int i = r;i > mid;i--){
        int tl = max(l,i - qr + 1),tr = min(mid,i - ql + 1);
        if(tl <= tr) maxx = max(maxx,pre[i] + st2.query(tl,tr));
        if(maxx != INF) ans[i] = max(ans[i],maxx);
    }
}
signed main(){
    n = read();
    for(int i = 1;i <= n;i++){
        a[i] = read();
        pre[i] = pre[i - 1] + a[i];
    }
    for(int i = 1;i <= n;i++){
        st1.maxx[0][i] = pre[i];
        st2.maxx[0][i] = -pre[i - 1];
    }
    st1.init();
    st2.init();
    int q = read();
    while(q--){
    	ql = read();
    	qr = read();
        fill(ans + 1,ans + n + 1,INF);
        solve(1,n);
        unsigned int c = 0;
        for(int i = 1;i <= n;i++) c ^= i * ans[i];
        write(c);
        puts("");
    }
    return 0;
}

容易发现既然有了 ST 表，加上区间划分，容易想到倍增分块。时间复杂度 $O(nq + n \log n)$，AC $100pts$。

// 100 pts
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[50005],ans[50005],b[50005],pre1[50005],pre2[50005],q1[50005],q2[50005],f[50005],g[25][25][50005];
map<pair<int,int>,unsigned int> mp;
void solve(int l,int r,int ans[]){
	if(l > r) return;
	int cur = l - 1,l1 = 1,l2 = 1,r1 = 0,r2 = 0;
	for(int i = 1;i <= n;i++){
		while(cur + 1 <= n && cur + 1 <= i + r - 1){
			cur++;
			while(l1 <= r1 && pre1[q1[r1]] <= pre1[cur]) r1--;
			q1[++r1] = cur;
		}
		if(l1 <= r1 && q1[l1] < i + l - 1) l1++;
		if(l1 <= r1) f[i] = pre1[q1[l1]] - pre1[i - 1];
		else f[i] = -0x3f3f3f3f;
		while(l2 <= r2 && f[q2[r2]] <= f[i]) r2--;
		q2[++r2] = i;
		if(l2 <= r2 && i - q2[l2] + 1 > l) l2++;
		if(l2 <= r2) ans[i] = max(ans[i],f[q2[l2]]);
	}
	cur = l - 1;
	l1 = l2 = 1;
    r1 = r2 = 0;
	for(int i = 1;i <= n;i++){
		while(cur + 1 <= n && cur + 1 <= i + r - 1){
			cur++;
			while(l1 <= r1 && pre2[q1[r1]] <= pre2[cur]) r1--;
			q1[++r1] = cur;
		}
		if(l1 <= r1 && q1[l1] < i + l - 1) l1++;
		if(l1 <= r1) f[i] = pre2[q1[l1]] - pre2[i - 1];
		else f[i] = -0x3f3f3f3f;
		while(l2 <= r2 && f[q2[r2]] <= f[i]) r2--;
		q2[++r2] = i;
		if(l2 <= r2 && i - q2[l2] + 1 > l) l2++;
		if(l2 <= r2) ans[n - i + 1] = max(ans[n - i + 1],f[q2[l2]]);
	}
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
		b[i] = a[i];
	}
	reverse(b + 1,b + n + 1);
	for(int i = 1;i <= n;i++){
		pre1[i] = pre1[i - 1] + a[i];
        pre2[i] = pre2[i - 1] + b[i];
    }
	memset(g,-0x3f3f3f3f,sizeof g);
	for(int i = 0;i < 17;i++) solve(1 << i,(1 << (i + 1)) - 1,g[i][i]);
	for(int i = 0;i < 17;i++){
		for(int j = i + 1;j < 17;j++){
			for(int k = 1;k <= n;k++) g[i][j][k] = max(g[j][j][k],g[i][j - 1][k]);
        }
    }
	int q; cin >> q;
	while(q--){
		int l,r; cin >> l >> r;
		if(mp.count(make_pair(l,r))){
			cout << mp[make_pair(l,r)] << "\n";
			continue;
		}
		int x = ceil(log2(l)),y = log2(r);
		memset(ans,-0x3f3f3f3f,sizeof ans);
		if(l * 2 <= r){
			if((1 << x) - 1 <= r) solve(l,(1 << x) - 1,ans);
			else solve(l,r,ans);
			if((1 << y) >= l) solve(1 << y,r,ans);
			else solve(l,r,ans);
		}else solve(l,r,ans);
		unsigned int c = 0;
		for(int i = 1;i <= n;i++){
			if(x <= y - 1) ans[i] = max(ans[i],g[x][y - 1][i]);
			c ^= i * ans[i];
		}
		mp[make_pair(l,r)] = c;
		cout << c << "\n";
	}
    return 0;
}

upd on 2025/12/06：记得卡常，要不然会 TLE 几个点。