发现一个结论，就是说这个道路怎么走答案其实是一样的。
然后就能愉快暴力了。。。
话说为何班长每次暴力都能 \(Ac\)
但是我们要倍增！！！
然后就行了。。。
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define sb(x) cout<<#x" = "<<x<<‘ ‘
#define jb(x) cout<<#x" = "<<x<<endl
#define debug cout<<"debug"<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;
class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &s)
{
register int f = 0;s = 0; register char ch = gc();
while(!isdigit(ch)) {f |= ch == ‘-‘; ch = gc();}
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+7; const ll llinf = 1e18+7;
#define int long long
namespace xin
{
class xin_edge{public:int next,ver,w;}edge[maxn];
int head[maxn],rp;
auto add = [](int x,int y,int z) -> void {edge[++rp].ver = y; edge[rp].w = z; edge[rp].next = head[x]; head[x] = rp;};
int siz[maxn],d[maxn],fa[maxn],top[maxn],hson[maxn],mi[23],he[maxn],c[maxn],sum[maxn],f[maxn][23],ton[maxn];
int n,k,m,tot,logms;
void dfs1(int x,int f)
{
d[x] = d[f] + 1; siz[x] = 1; fa[x] = f;
go(i,x)
{
if(y == f) continue;
c[y] = edge[i].w; dfs1(y,x); siz[x] += siz[y];
if(siz[y] > siz[hson[x]]) hson[x] = y;
}
}
void dfs2(int x,int t)
{
top[x] = t; if(hson[x]) dfs2(hson[x],t);
go(i,x)
{
if(y == hson[x] or y == fa[x]) continue;
dfs2(y,y);
}
}
void dfs(int x)
{
auto find = []() -> int
{
register int lim = sum[tot] + k,l = 0,r = tot,ret = 0;
while(l <= r)
{
register int mid = l + r >> 1;
if(sum[mid] >= lim) ret = mid,l = mid + 1;
else r = mid - 1;
}
return ton[ret];
};
ton[++tot] = x; sum[tot] = sum[tot - 1] - c[x];
f[x][0] = find();// jb(f[x][0]);
try(i,1,logms) f[x][i] = f[f[x][i-1]][i-1];
go(i,x)
{
if(y == fa[x]) continue;
he[y] = he[x] + c[y];
dfs(y);
}
tot --;
}
inline short main()
{
io >> n >> k; logms = log2(n) + 1ll;
// jb(logms);
try(i,1,n-1)
{
register int x,y,z; io >> x >> y >> z;
add(x,y,z); add(y,x,z);
}
auto prework = [=]() -> void {mi[0] = 1; try(i,1,logms) mi[i] = mi[i-1] << 1;sum[0] = llinf;}; prework();
dfs1(1,0); dfs2(1,1);
dfs(1);
// try(i,1,n) try(j,0,logms) sb(i),sb(j),jb(f[i][j]);
auto query = [=](int s,int t)mutable -> int
{
auto lca = [s,t]()mutable -> int
{
while(top[s] xor top[t])
{
if(d[top[s]] < d[top[t]]) s ^= t ^= s ^= t;
s = fa[top[s]];
}
return d[s] > d[t] ? t : s;
};
register int ans = 0,allca = lca();
throw(i,logms,0) if(d[f[s][i]] >= d[allca]) s = f[s][i],ans += mi[i];
throw(i,logms,0) if(d[f[t][i]] >= d[allca]) t = f[t][i],ans += mi[i];
if(he[t] - he[allca] >= k - (he[s] - he[allca])) return ans + 1; return ans;
};
io >> m;
try(i,1,m){register int s,t; io >> s >> t;printf("%lld\n",query(s,t));}
return 0;
}
}
signed main() {return xin::main();}
首先想到垃圾基础 \(dp\)
就是：
然后愉快 \(\mathcal O(n^2)\)
然后这就是暴力。。
但是为啥只给 \(20pts\)
靠。。。。
然后正解我们加一个分治。
从中间断开。
然后 \(f_{i,1/0,1/0}\) 表示第 \(i\) 个，然后 \(mid\) 能不能选，然后是选了没选。
转移也很简单。。
l[i][1][1] = l[i+1][1][0] + a[i]; l[i][1][0] = max(l[i+1][1][1],l[i+1][1][0]);
l[i][0][1] = l[i+1][0][0] + a[i]; l[i][0][0] = max(l[i+1][0][1],l[i+1][0][0]);
l[i][1][1] = max(l[i][1][1],l[i][1][0]),l[i][0][1] = max(l[i][0][0],l[i][0][1]);
r[i][1][1] = r[i-1][1][0] + a[i]; r[i][1][0] = max(r[i-1][1][1],r[i-1][1][0]);
r[i][0][1] = r[i-1][0][0] + a[i]; r[i][0][0] = max(r[i-1][0][1],r[i-1][0][0]);
r[i][1][1] = max(r[i][1][1],r[i][1][0]),r[i][0][1] = max(r[i][0][0],r[i][0][1]);
然后代码：
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define sb(x) cout<<#x" = "<<x<<‘ ‘
#define jb(x) cout<<#x" = "<<x<<endl
#define debug cout<<"debug"<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;
class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &s)
{
register int f = 0;s = 0; register char ch = gc();
while(!isdigit(ch)) {f |= ch == ‘-‘; ch = gc();}
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+7; const ll llinf = 1e18+7;
#define int long long
namespace xin
{
const int mod = 998244353;
int a[maxn],l[maxn][2][2],r[maxn][2][2],tl[maxn],tr[maxn];
int n,ans = 0;
auto max = [](int x,int y) -> int {return x > y ? x : y;};
void dfs(int ql,int qr)
{
if(qr - ql == 0) return (ans += a[qr]) %= mod,void();
if(qr - ql == 1) return (ans += max(a[ql],a[qr]) + a[ql] + a[qr]) %= mod,void();
register int mid = ql + qr >> 1;
dfs(ql,mid); dfs(mid+1,qr);
l[mid][1][1] = a[mid]; r[mid+1][1][1] = a[mid+1];
l[mid][1][0] = l[mid][0][0] = r[mid+1][1][0] = r[mid+1][0][0] = 0;
throw(i,mid-1,ql)
{
l[i][1][1] = l[i+1][1][0] + a[i]; l[i][1][0] = max(l[i+1][1][1],l[i+1][1][0]);
l[i][0][1] = l[i+1][0][0] + a[i]; l[i][0][0] = max(l[i+1][0][1],l[i+1][0][0]);
}
throw(i,mid-1,ql)
l[i][1][1] = max(l[i][1][1],l[i][1][0]),l[i][0][1] = max(l[i][0][0],l[i][0][1]);
try(i,mid+2,qr)
{
r[i][1][1] = r[i-1][1][0] + a[i]; r[i][1][0] = max(r[i-1][1][1],r[i-1][1][0]);
r[i][0][1] = r[i-1][0][0] + a[i]; r[i][0][0] = max(r[i-1][0][1],r[i-1][0][0]);
}
try(i,mid+2,qr)
r[i][1][1] = max(r[i][1][1],r[i][1][0]),r[i][0][1] = max(r[i][0][0],r[i][0][1]);
try(i,ql,mid) tl[i] = max(l[i][1][1] - l[i][0][1],0);
try(i,mid+1,qr) tr[i] = max(r[i][1][1] - r[i][0][1],0);
std::sort(tl+ql,tl+mid+1); std::sort(tr+mid+1,tr+qr+1);
register int temp = 0;
try(i,ql,mid) (temp += l[i][0][1]) %= mod; (temp *= (qr - mid)) %= mod;
(ans += temp) %= mod; temp = 0;
try(i,mid+1,qr) (temp += r[i][0][1]) %= mod;
(ans += temp * (mid - ql + 1) % mod) %= mod;
register int zhi = mid;
try(i,ql,mid)
{
while(zhi < qr and tr[zhi+1] <= tl[i]) zhi ++;
(ans += (zhi - mid) * tl[i] % mod) %= mod;
}
zhi = ql-1;
try(i,mid+1,qr)
{
while(zhi < mid and tl[zhi+1] < tr[i]) zhi ++;
(ans += (zhi - ql + 1) * tr[i] % mod) %= mod;
}
}
inline short main()
{
io >> n;
try(i,1,n) io >> a[i];
dfs(1,n);
cout<<ans<<endl;
return 0;
}
}
signed main() {return xin::main();}
我只会 \(90pts\) 算法。
就是一个时间一个时间的看。
然后统计，
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
#define sb(x) cout<<#x" = "<<x<<‘ ‘
#define jb(x) cout<<#x" = "<<x<<endl
#define debug cout<<"debug"<<endl
#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll;// typedef unsigned long long ull;
class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &s)
{
register int f = 0;s = 0; register char ch = gc();
while(!isdigit(ch)) {f |= ch == ‘-‘; ch = gc();}
while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
}}io;
}
using namespace xin_io; static const int maxn = 1e7+10,inf = 1e9+7; const ll llinf = 1e18+7;
#define int long long
namespace xin
{
const int mod = 998244353;
typedef unsigned long long u64;
auto ksm = [](int x,int y,int ret = 1) -> int
{
while(y)
{
if(y & 1) ret = ret * x % mod;
x = x * x % mod; y >>= 1;
}
return ret;
};
u64 xorshift128p(u64 &A, u64 &B) {
u64 T = A, S = B;
A = S;
T ^= T << 23;
T ^= T >> 17;
T ^= S ^ (S >> 26);
B = T;
return T + S;
}
void gen(int n, int L, int X, int Y, u64 A, u64 B, int l[], int r[]) {
for (int i = 1; i <= n; i ++) {
l[i] = xorshift128p(A, B) % L + X;
r[i] = xorshift128p(A, B) % L + Y;
if (l[i] > r[i]) std::swap(l[i], r[i]);
}
}
int l[maxn],r[maxn],nl[maxn],nr[maxn];
int n,L,X,Y;
u64 A,B;
int ans = 0;
bool vis[maxn];
int f[maxn];
int q1[maxn],q2[maxn],zhi1 = 0,zhi2 = 0;
int tim = 0,wan = 0;
inline short main()
{
io >> n >> L >> X >> Y >> A >> B;
gen(n,L,X,Y,A,B,l,r);
try(i,1,n) q1[++zhi1] = i;
// try(i,1,n) sb(l[i]),jb(r[i]);
while(1)
{
tim++;
while(zhi1)
{
register int x = q1[zhi1 --];
q2[++zhi2] = x;
auto max = [](int x,int y) -> int {return x > y ? x : y;};
auto min = [](int x,int y) -> int {return x < y ? x : y;};
register int newl = max(l[x],max(l[x-1],l[x+1])),newr = min(r[x],min(r[x+1],r[x-1]));
if(newl == l[x]) newl ++;
if(newr == r[x]) newr --;
// sb(newl); jb(newr);
if(newr < newl or !newr or !newl)
{
vis[x] = 1;
wan ++;
f[x] = tim;
nl[x] = nr[x] = 0;
}
else nl[x] = newl,nr[x] = newr;
}
while(zhi2)
{
register int x = q2[zhi2 --];
l[x] = nl[x]; r[x] = nr[x];
if(!vis[x]) q1[++zhi1] = x;
}
if(n == wan) break;
}
// try(i,1,n) sb(i),jb(f[i]);
try(i,1,n) (ans += ksm(3,i-1) * f[i] % mod) %= mod;
cout<<ans<<endl;
return 0;
}
}
signed main() {return xin::main();}
原文：https://www.cnblogs.com/NP2Z/p/15270555.html