题解 SP1043 【GSS1 - Can you answer these queries I】
Great_Influence · · 题解
猫树模板题。
在一般的数据下，本题可以直接在
但是如果
我们需要一种支持
那么，有没有一种数据结构支持
猫树。
本题就是猫锟举的第一个例子。
为了解决问题，我们需要预处理区间最大子段和和区间最大中心和(指从当前节点到达区间中心的连续和)。这个可以简单做到
因此，总时间复杂度为
经过测试，下面的题解(借用一下)在
代码:
#include<bits/stdc++.h>
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define Forward(i,a,b) for(i=(a);i>=(b);--i)
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
#define Chkmin(a,b) a=a<b?a:b
using namespace std;
template<typename T>inline void read(T &x)
{
T f=1;x=0;char c;
for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=x*10+(c^48);
x*=f;
}
inline void write(int x)
{
if(x<0)putchar('-'),x*=-1;
if(!x)putchar(48);
static int sta[45],tp;
for(tp=0;x;x/=10)sta[++tp]=x%10;
for(;tp;putchar(sta[tp--]^48));
putchar('\n');
}
void file()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
}
const int MAXN=(1<<19)+7;
static int n,m,a[MAXN],len,Log2[MAXN],pos[MAXN];
namespace Meow_Tree
{
static int p[21][MAXN],s[21][MAXN];//区间最大子段和，区间最大前缀和
void build_tree(int h,int l,int r,int dps)
{
if(l==r){pos[l]=h;return;}
int mid=(l+r)>>1,prep,sm;
p[dps][mid]=s[dps][mid]=sm=a[mid];
prep=a[mid];
if(sm<0)sm=0;
Repe(i,mid-1,l)
{
prep+=a[i];sm+=a[i];
s[dps][i]=max(s[dps][i+1],prep);
p[dps][i]=max(p[dps][i+1],sm);
if(sm<0)sm=0;
}
p[dps][mid+1]=s[dps][mid+1]=sm=a[mid+1];
prep=a[mid+1];
if(sm<0)sm=0;
Rep(i,mid+2,r)
{
prep+=a[i];sm+=a[i];
s[dps][i]=max(s[dps][i-1],prep);
p[dps][i]=max(p[dps][i-1],sm);
if(sm<0)sm=0;
}
build_tree(h<<1,l,mid,dps+1);
build_tree(h<<1|1,mid+1,r,dps+1);
}
inline int query(int l,int r)
{
if(l==r)return a[l];
static int dps;dps=Log2[pos[l]]-Log2[pos[l]^pos[r]];
return max(max(p[dps][l],p[dps][r]),s[dps][l]+s[dps][r]);
}
}
using namespace Meow_Tree;
inline void init()
{
read(n);
Rep(i,1,n)read(a[i]);
len=2;while(len<n)len<<=1;
Rep(i,2,len<<1)Log2[i]=Log2[i>>1]+1;
build_tree(1,1,len,1);
}
inline void solve()
{
read(m);
static int l,r;
Rep(i,1,m)read(l),read(r),write(query(l,r));
}
int main()
{
file();
init();
solve();
cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}附猫锟的代码:
#include<bits/stdc++.h>
using namespace std;
#define RG register
#define IL __inline__ __attribute__((always_inline))
#define For(i, a, b) for(RG int i = a, ___u = b; i <= ___u; ++i)
#define Dor(i, a, b) for(RG int i = b, ___d = a; i >= ___d; --i)
#define Rep(i, a, b) for(RG int i = a, ___u = b; i != ___u; ++i)
#define dmin(a, b) ((a) < (b) ? (a) : (b))
#define dmax(a, b) ((a) > (b) ? (a) : (b))
#define cmin(a, b) ((a) > (b) ? (a) = (b) : 1)
#define cmax(a, b) ((a) < (b) ? (a) = (b) : 1)
#define ddel(a, b) ((a) > (b) ? (a) - (b) : (b) - (a))
#define dabs(i) ((i) > 0 ? (i) : -(i))
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef long double ld;
#include <queue>
#include <vector>
namespace pb_ds
{
// 输入输出优化模板从此开始
namespace io
{
const int MaxBuff = 1 << 15;
const int Output = 1 << 23;
char B[MaxBuff], *S = B, *T = B;
//#define getc() getchar()
#define getc() ((S == T) && (T = (S = B) + fread(B, 1, MaxBuff, stdin), S == T) ? 0 : *S++)
char Out[Output], *iter = Out;
IL void flush()
{
fwrite(Out, 1, iter - Out, stdout);
iter = Out;
}
}
template<class Type> IL Type read()
{
using namespace io;
RG char ch; RG Type ans = 0; RG bool neg = 0;
while(ch = getc(), (ch < '0' || ch > '9') && ch != '-') ;
ch == '-' ? neg = 1 : ans = ch - '0';
while(ch = getc(), '0' <= ch && ch <= '9') ans = ans * 10 + ch - '0';
return neg ? -ans : ans;
}
template<class Type> IL void Print(RG Type x, RG char ch = '\n')
{
using namespace io;
if(!x) *iter++ = '0';
else
{
if(x < 0) *iter++ = '-', x = -x;
static int s[100]; RG int t = 0;
while(x) s[++t] = x % 10, x /= 10;
while(t) *iter++ = '0' + s[t--];
}
*iter++ = ch;
}
// 输入输出优化模板到此结束
const int MaxN = 200010;
const ll inf = 1000000000000000000ll;
int val[MaxN], pos[MaxN];
struct Node
{
struct Data {ll pre, sum;} *dl, *dr;
int mov_l, mov_r;
IL ll query(RG int l, RG int r)
{
return dl[l -= mov_l].sum > dr[r -= mov_r].sum
? dmax(dl[l].sum, dl[l].pre + dr[r].pre)
: dmax(dr[r].sum, dl[l].pre + dr[r].pre);
}
} T[524288];
int N;
void build(RG int i, RG int l, RG int r)
{
if(l + 1 == r || N <= l) return;
RG int m = (l + r) >> 1;
build(i << 1, l, m);
build(i << 1 | 1, m, r);
RG Node *o = T + i;
o->dl = new Node::Data[m - l], o->mov_l = l;
o->dr = new Node::Data[r - m], o->mov_r = m;
RG ll pre, max_pre, sum, max_sum;
pre = sum = 0, max_pre = max_sum = -inf;
for(RG int k = m - 1; k >= l; --k)
{
pre += val[k], cmax(max_pre, pre);
sum = dmax(sum, 0) + val[k], cmax(max_sum, sum);
o->dl[k - l] = (Node::Data) {max_pre, max_sum};
}
pre = sum = 0, max_pre = max_sum = -inf;
for(RG int k = m; k <= r - 1; ++k)
{
pre += val[k], cmax(max_pre, pre);
sum = dmax(sum, 0) + val[k], cmax(max_sum, sum);
o->dr[k - m] = (Node::Data) {max_pre, max_sum};
}
}
int pre[1024];
IL void main()
{
RG int (*F)() = read<int>;
RG int n = N = F();
Rep(i, 0, n) val[i] = F();
RG int D = 1; while(D < n) D <<= 1;
build(1, 0, D);
RG int l, r, d, v;
pre[0] = 0;
Rep(i, 1, 1024) pre[i] = pre[i >> 1] + 1;
Rep(_, 0, F())
{
l = F() - 1, r = F() - 1;
if(l == r) Print(val[l]);
else
{
l += D, r += D;
v = l ^ r;
d = (v < 1024 ? pre[v] : 10 + pre[v >> 10]);
Print(T[l >> d].query(l - D, r - D));
}
}
io::flush();
}
}
int main()
{
pb_ds::main();
fclose(stdin), fclose(stdout);
cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
}