[bzoj4003]城市攻占

倍增，对于每一个点计算他走到$2^i$次祖先所需要的攻击力以及最终会变成什么（一个一次函数），简单处理即可
（然而这样是错的，因为他只保证了骑士的攻击力可以存，并没有保证这个一次函数的系数可以存）
（其实还可以用科学记数法即pair<long double,int>来存即可，只要注意精度&常数）
正解是模拟，维护当前子树中骑士血量的左偏树（支持合并），然后考虑不断删除堆顶，修改可以用打标记来实现（因为乘的是正的，所以不改变顺序）

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 300005

 4 #define ll long long

 5 struct ji{

 6     int nex,to,len;

 7 }edge[N<<1];

 8 pair<ll,int>val[N];

 9 int E,n,m,x,r[N],dis[N],ls[N],rs[N],head[N],d[N],p[N],ans1[N],ans2[N];

10 ll y,tc[N],tj[N],h[N],v[N];

11 void upd(int k,ll x,ll y){

12     tc[k]=tc[k]*x;

13     tj[k]=tj[k]*x+y;

14     val[k].first=val[k].first*x+y;

15 }

16 void down(int k){

17     upd(ls[k],tc[k],tj[k]);

18     upd(rs[k],tc[k],tj[k]);

19     tc[k]=1;

20     tj[k]=0;

21 }

22 int merge(int x,int y){

23     if ((!x)||(!y))return x+y;

24     down(x);

25     down(y);

26     if (val[x]>val[y])swap(x,y);

27     rs[x]=merge(rs[x],y);

28     if (dis[ls[x]]<dis[rs[x]])swap(ls[x],rs[x]);

29     dis[x]=dis[rs[x]]+1;

30     return x;

31 }

32 void add(int x,int y){

33     edge[E].nex=head[x];

34     edge[E].to=y;

35     head[x]=E++;

36 }

37 void dfs(int k,int sh){

38     d[k]=sh;

39     for(int i=head[k];i!=-1;i=edge[i].nex){

40         dfs(edge[i].to,sh+1);

41         r[k]=merge(r[k],r[edge[i].to]);

42     }

43     while ((r[k])&&(val[r[k]].first<h[k])){

44         down(r[k]);

45         ans1[k]++;

46         ans2[r[k]]=d[val[r[k]].second]-d[k];

47         r[k]=merge(ls[r[k]],rs[r[k]]);

48     }

49     if (!p[k])upd(r[k],1,v[k]);

50     else upd(r[k],v[k],0);

51 }

52 int main(){

53     scanf("%d%d",&n,&m);

54     memset(head,-1,sizeof(head));

55     for(int i=1;i<=n;i++)scanf("%lld",&h[i]);

56     for(int i=2;i<=n;i++){

57         scanf("%d%d%lld",&x,&p[i],&v[i]);

58         add(x,i);

59     }

60     for(int i=1;i<=m;i++){

61         scanf("%lld%d",&y,&x);

62         val[i]=make_pair(y,x);

63         tc[i]=1;

64         r[x]=merge(r[x],i);

65     }

66     dfs(1,0);

67     while (r[1]){

68         ans2[r[1]]=d[val[r[1]].second]+1;

69         r[1]=merge(ls[r[1]],rs[r[1]]);

70     }

71     for(int i=1;i<=n;i++)printf("%d\n",ans1[i]);

72     for(int i=1;i<=m;i++)printf("%d\n",ans2[i]);

73 }

巴特西

[bzoj4003]城市攻占

最新文章

热门文章