NC20554. [HNOI2015]开店
描述
输入描述
第一行三个用空格分开的数 n、Q和A，表示树的大小、开店的方案个数和妖怪的年龄上限。第二行n个用空格分开的数 x1、x2、…、xn，xi 表示第i 个地点妖怪的年龄，满足0 ≤ xi < A。(年龄是可以为0的，例如刚出生的妖怪的年龄为 0。)接下来 n-1 行，每行三个用空格分开的数 a、b、c，表示树上的顶点a和b之间有一条权为c(1 ≤ c ≤ 1000)的边，a和b是顶点编号。接下来Q行，每行三个用空格分开的数 u、a、 b。对于这Q行的每一行，用 a、b、A计算出 L和R，表示询问“在地方u开店，面向妖怪的年龄区间为[L,R]的方案的方便值是多少”。对于其中第 1 行，L 和 R 的计算方法为：L=min(a%A,b%A), R=max(a%A,b%A)。对于第 2到第 Q行，假设前一行得到的方便值为 ans，那么当前行的L和R计算方法为：L=min((a+ans)%A,(b+ans)%A), R=max((a+ans)%A,(b+ans)%A)。
输出描述
对于每个方案，输出一行表示方便值。
示例1
输入:
10 10 10 0 0 7 2 1 4 7 7 7 9 1 2 270 2 3 217 1 4 326 2 5 361 4 6 116 3 7 38 1 8 800 6 9 210 7 10 278 8 9 8 2 8 0 9 3 1 8 0 8 4 2 7 9 7 3 4 7 0 2 2 7 3 2 1 2 3 4
输出:
1603 957 7161 9466 3232 5223 1879 1669 1282 0
C++(g++ 7.5.0) 解法, 执行用时: 2579ms, 内存消耗: 182912K, 提交时间: 2022-09-23 20:09:54
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std ;
using ll = long long ;
using pii = pair<ll,ll> ;
const int N = 4e5 + 100,M = 2 * N ;
// 这里每个点都有一个年龄，现在题目需要求解出年龄在一个范围内
// 到达一个点的固定距离，使用点分树来维护即可
// 对于年龄我们离散化，离散化之后就最多 n 个
// 这道题我们使用动态开点的线段树
// 然后还是想之前一样，不需要真正的维护点分数的重心树结构
// 我们可以用一个vector来进行存储，写的也很快
int n,m,A ;
int h[N],w[M],e[M],ne[M],idx ;
int sz[N],nian[N] ;
vector<pii> root[N] ;
vector<vector<pii>> son[N] ; // 记录这个第i个儿子的根
struct Ponit{
int dist,gr,di ;
} ;
vector<Ponit> pn[N] ;
bool st[N] ;
void add(int a,int b,int c){
e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++ ;
}
int getsz(int u,int fa){
int tot = 1 ;
for(int i = h[u] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(j == fa || st[j]) continue ;
tot += getsz(j,u) ;
}
return tot ;
}
int getgravity(int u,int fa,int sum){
int gr = -1,mx = 0 ;
sz[u] = 1 ;
for(int i = h[u] ;~ i ; i = ne[i]){
int j = e[i] ;
if(j == fa || st[j]) continue ;
int nx = getgravity(j,u,sum) ;
if(nx != -1) gr = nx ;
sz[u] += sz[j] ;
mx = max(mx,sz[j]) ;
}
mx = max(mx,sum - sz[u]) ;
if(2 * mx <= sum) gr = u ;
return gr ;
}
void dfs(int u,int fa,int dist,int gr,int di){
root[gr].push_back({nian[u],dist}) ;
son[gr][di].push_back({nian[u],dist}) ;
pn[u].push_back({dist,gr,di}) ;
for(int i = h[u] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(j == fa || st[j]) continue ;
dfs(j,u,dist+w[i],gr,di) ;
}
}
void divtree(int u){
int tot = getsz(u,-1) ;
int gr = getgravity(u,-1,tot) ;
st[gr] = 1 ;
root[gr].push_back({nian[gr],0}) ;
pn[gr].push_back({0,gr,0}) ;
for(int i = h[gr],di = 0 ;~ i ; i = ne[i]){
int j = e[i] ;
if(st[j]) continue ;
son[gr].push_back({}) ;
dfs(j,gr,w[i],gr,di) ;
di ++ ;
}
for(int i = h[gr] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(st[j]) continue ;
divtree(j) ;
}
}
ll calc(vector<pii> &v,int l,int r,int dist){
pii L = {l,0},R = {r+1,0} ;
int lid = lower_bound(v.begin(), v.end(),L) - v.begin() ;
int rid = lower_bound(v.begin(), v.end(),R) - v.begin() - 1 ;
if(lid == v.size() || lid > rid) return 0ll ;
return (ll)dist * (rid - lid + 1) + v[rid].second - (lid ? v[lid-1].second : 0) ;
}
ll query(int u,int l,int r){
ll ans = 0 ;
for(Ponit t : pn[u]){
// cout << " ---------> " << t.gr << " \n" ;
if(t.gr == u){ // 当前自己就是重心，那么就可以进行直接查了
ans += calc(root[u],l,r,t.dist) ;
continue ;
}
ans += calc(root[t.gr],l,r,t.dist) ;
ans -= calc(son[t.gr][t.di],l,r,t.dist) ;
}
return ans ;
}
int main(){
scanf("%d%d%d",&n,&m,&A) ;
for(int i = 1 ; i <= n ; i ++) scanf("%d",&nian[i]) ;
memset(h,-1,sizeof h) ;
for(int i = 1 ; i <= n - 1 ; i ++){
int a,b,c ;
scanf("%d%d%d",&a,&b,&c) ;
add(a,b,c),add(b,a,c) ;
}
divtree(1) ;
for(int i = 1 ; i <= n ; i ++){
sort(root[i].begin(), root[i].end()) ;
for(int j = 1 ; j < root[i].size() ; j ++)
root[i][j].second += root[i][j-1].second ;
for(vector<pii> &t : son[i]){
sort(t.begin(), t.end()) ;
for(int j = 1 ; j < t.size() ; j ++)
t[j].second += t[j-1].second ;
}
}
ll ans = 0 ;
while(m --){
ll u,a,b,zz ;
scanf("%lld%lld%lld",&u,&a,&b) ;
ll L = min((a + ans) % A,(b + ans) % A),R = max((a + ans) % A,(b + ans)% A) ;
ans = query(u,L,R) ;
printf("%lld\n",ans) ;
}
return 0 ;
}
C++14(g++5.4) 解法, 执行用时: 1437ms, 内存消耗: 166760K, 提交时间: 2019-10-29 22:12:30
// luogu-judger-enable-o2
// luogu-judger-enable-o2
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=150000+10;
struct node { int age,id; } a[N];
bool operator <(node a,node b) {
if (a.age==b.age) return a.id<b.id;
else return a.age<b.age;
}
int n,Q,A;
//邻接表
struct Edge { int v,w,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v,int w) {
static int cnt=0;
e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}
//树剖
int sz[N],dis[N],fa[N],hson[N];
int dfn[N],top[N],dfs_clock=0;
ll sume[N],sumdis[N];
inline void dfs1(int u,int f) {
fa[u]=f,sz[u]=1;
for (re int i=head[u];i;i=e[i].nxt) {
int v=e[i].v,w=e[i].w; if (v==f) continue;
dis[v]=dis[u]+w; dfs1(v,u); sz[u]+=sz[v];
if (!hson[u]||sz[v]>sz[hson[u]]) hson[u]=v;
}
}
inline void dfs2(int u,int anc) {
top[u]=anc,dfn[u]=++dfs_clock;
sume[dfs_clock]=dis[u]-dis[fa[u]];
if (hson[u]) dfs2(hson[u],anc);
for (re int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
if (v!=fa[u]&&v!=hson[u]) dfs2(v,v);
}
}
//主席树
int rt[N],tot=0;
struct treenode { int ls,rs,tim; ll s; } t[N*100];
inline void build(int& o,int l,int r) {
o=++tot; if (l==r) return;
int mid=(l+r)>>1;
build(t[o].ls,l,mid),build(t[o].rs,mid+1,r);
}
inline void modify(int& o,int l,int r,int ql,int qr) {
t[++tot]=t[o],o=tot;
if (l==ql&&r==qr) { ++t[o].tim; return; }
t[o].s+=sume[qr]-sume[ql-1];
int mid=(l+r)>>1;
if (ql<=mid) modify(t[o].ls,l,mid,ql,min(qr,mid));
if (qr>mid) modify(t[o].rs,mid+1,r,max(ql,mid+1),qr);
}
inline ll query(int o,int l,int r,int ql,int qr) {
ll res=1ll*(sume[qr]-sume[ql-1])*t[o].tim;
if (l==ql&&r==qr) return res+t[o].s;
int mid=(l+r)>>1;
if (ql<=mid) res+=query(t[o].ls,l,mid,ql,min(qr,mid));
if (qr>mid) res+=query(t[o].rs,mid+1,r,max(ql,mid+1),qr);
return res;
}
inline ll ask(int u,int k) {
ll res=0;
while (top[u]!=1) {
res+=query(rt[k],1,n,dfn[top[u]],dfn[u]);
u=fa[top[u]];
}
res+=query(rt[k],1,n,1,dfn[u]);
return res;
}
int main() {
n=read(),Q=read(),A=read();
for (re int i=1;i<=n;++i) a[i].age=read(),a[i].id=i;
sort(a+1,a+n+1);
for (re int i=1;i<n;++i) {
int u=read(),v=read(),w=read();
addEdge(u,v,w),addEdge(v,u,w);
}
dfs1(1,0),dfs2(1,1);
for (re int i=1;i<=n;++i) {
sume[i]+=sume[i-1];
sumdis[i]=sumdis[i-1]+dis[a[i].id];
}
build(rt[0],1,n);
for (re int i=1;i<=n;++i) {
int u=a[i].id; rt[i]=rt[i-1];
while (top[u]!=1) {
modify(rt[i],1,n,dfn[top[u]],dfn[u]);
u=fa[top[u]];
}
modify(rt[i],1,n,1,dfn[u]);
}
ll lastans=0;
for (re int i=1;i<=Q;++i) {
int u=read(),l=read(),r=read();
l=(1ll*l+lastans)%A,r=(1ll*r+lastans)%A;
if (l>r) swap(l,r);
l=lower_bound(a+1,a+n+1,(node){l,0})-a;
r=upper_bound(a+1,a+n+1,(node){r,n})-a-1;
lastans=1ll*(r-l+1)*dis[u]+(sumdis[r]-sumdis[l-1])-2*(ask(u,r)-ask(u,l-1));
printf("%lld\n",lastans);
}
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 848ms, 内存消耗: 156700K, 提交时间: 2022-08-09 20:53:51
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define F first
#define S second
using namespace std;
const int maxn=150000+10;
const int inf=0x3f3f3f3f;
int n,q,A,val[maxn],head[maxn],tot;pii a[maxn];
int dep[maxn],top[maxn],siz[maxn],son[maxn],fa[maxn],id[maxn],tim;
int T[maxn],L[maxn*100],R[maxn*100],cnt;ll dis[maxn],sumE[maxn],sumdis[maxn],sum[maxn*100],lazy[maxn*100];
struct node{
int to,next,val;
}e[maxn<<1];
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
inline void addedge(int x,int y,int w){
e[++tot].to=y;
e[tot].val=w;
e[tot].next=head[x];
head[x]=tot;
}
void dfs1(int x,int f){
siz[x]=1;fa[x]=f;
dep[x]=dep[f]+1;
int maxson=-1;
for(int i=head[x],y;i;i=e[i].next){
y=e[i].to;
if(y==f) continue;
val[y]=e[i].val;
dis[y]=dis[x]+e[i].val;
dfs1(y,x);
siz[x]+=siz[y];
if(siz[y]>maxson){
maxson=siz[y];
son[x]=y;
}
}
}
void dfs2(int x,int topf){
id[x]=++tim;
sumE[tim]=val[x];
top[x]=topf;
if(son[x]) dfs2(son[x],topf);
for(int i=head[x],y;i;i=e[i].next){
y=e[i].to;
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
void update(int &now,int pre,int Le,int Ri,int l,int r){
now=++cnt;L[now]=L[pre];R[now]=R[pre];lazy[now]=lazy[pre];
sum[now]=sum[pre]+(sumE[min(Ri,r)]-sumE[max(Le,l)-1]);
if(Le <= l && r <= Ri){
lazy[now]++;
return ;
}
int mid=(l+r)>>1;
if(Le <= mid) update(L[now],L[pre],Le,Ri,l,mid);
if(Ri > mid) update(R[now],R[pre],Le,Ri,mid+1,r);
}
ll query(int u,int v,int Le,int Ri,int l,int r){
if(Le <= l && r <= Ri) return sum[v]-sum[u];
int mid=(l+r)>>1;ll ans=(lazy[v]-lazy[u])*(sumE[min(Ri,r)]-sumE[max(Le,l)-1]);
if(Le <= mid) ans+=query(L[u],L[v],Le,Ri,l,mid);
if(Ri > mid) ans+=query(R[u],R[v],Le,Ri,mid+1,r);
return ans;
}
inline void modify(int i,int x){
T[i]=T[i-1];
while(top[x]!=1){
update(T[i],T[i],id[top[x]],id[x],1,n);
x=fa[top[x]];
}
update(T[i],T[i],1,id[x],1,n);
}
inline ll ask(int u,int v,int x){
ll ans=0;
while(top[x]!=1){
ans+=query(T[u],T[v],id[top[x]],id[x],1,n);
x=fa[top[x]];
}
ans+=query(T[u],T[v],1,id[x],1,n);
return ans;
}
int main()
{
n=read(),q=read(),A=read();
int x,y,w;
for(int i=1;i<=n;i++) a[i]=mp(read(),i);
for(int i=1;i<n;i++){
x=read(),y=read(),w=read();
addedge(x,y,w);addedge(y,x,w);
}
dfs1(1,0);dfs2(1,1);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) sumE[i]+=sumE[i-1],sumdis[i]=sumdis[i-1]+dis[a[i].S];
for(int i=1;i<=n;i++) modify(i,a[i].S);
int u,l,r;ll lastans=0;
while(q--){
u=read(),l=read(),r=read();
x=(l+lastans)%A;y=(r+lastans)%A;
if(x>y) swap(x,y);
l=lower_bound(a+1,a+n+1,mp(x,0))-a;
r=upper_bound(a+1,a+n+1,mp(y,inf))-a-1;
printf("%lld\n",lastans=dis[u]*(r-l+1)+(sumdis[r]-sumdis[l-1])-2*ask(l-1,r,u));
lastans%=A;
}
return 0;
}