nowcoder 牛客练习赛109

發表於 更新於 分類於 Disqus： 文章字數： 1.4k 所需閱讀時間 ≈ 5 分鐘
E(点分治)F(不看题解不懂题意)

https://ac.nowcoder.com/acm/contest/51721

E - 有向树

n点树,点上有值a[i]

所有边可正向可反向(2种状态)

一个具体的图的价值 = 图中 u可达v ,则贡献 |a[u]-a[v]|

求边所有2^{n-1}个图的价值和

范围

n 2e5

ai [1,1e9]

1s

256MB

我的思路

显然 u..->..v的贡献 了2^{n-1-length(u,v)}次

提出来前面 就相当于边权1/2了

想的是 树上启发式合并

这样 每次节点的合并都是 小点向大点合并， 重儿子就是全部成靠移动和全部乘上1/2, 上个线段树

这样 似乎是 O(n (log n)^2) 吗?

只过了21~28%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define mid (l+r)/2
ll read(){ll r;scanf("%lld",&r);return r;}
namespace CMM{
  const int _mod = 998244353;
  class modint{
    private:
      long long _v;
    public:
      modint() :_v(0) {  }
      modint(long long _a) {
        _v = (_a < 0)? _mod - ((-_a) % _mod) : (_a % _mod);
      }

      int val()const { return _v; }
      modint operator+()const { return *this; }
      modint operator-()const { return { _mod - _v }; }
      modint operator+(const modint& rhs) const { return modint(*this) += rhs; }
      modint operator-(const modint& rhs) const { return modint(*this) -= rhs; }
      modint operator*(const modint& rhs) const { return modint(*this) *= rhs; }
      modint operator/(const modint& rhs) const { return modint(*this) /= rhs; }

      bool operator==(const modint& rhs)const { return _v == rhs._v; }
      bool operator!=(const modint& rhs)const { return _v != rhs._v; }
      bool operator> (const modint& rhs)const { return _v >  rhs._v; }
      bool operator>=(const modint& rhs)const { return _v >= rhs._v; }
      bool operator<=(const modint& rhs)const { return _v <= rhs._v; }
      bool operator< (const modint& rhs)const { return _v <  rhs._v; }

      modint& operator+=(const modint& rhs) {
        (_v += rhs._v) %= _mod;
        return *this;
      }
      modint& operator-=(const modint& rhs) {
        (_v += _mod - rhs._v) %= _mod;
        return *this;
      }
      modint& operator*=(const modint& rhs) {
        _v = _v * rhs.val() % _mod;
        return *this;
      }
      modint& operator/=(const modint& rhs) { // 费马小定理
        _v = _v * rhs.inv().val() % _mod ;
        return *this;
      }
      modint pow(long long pwr) const {
        long long res(1);
        long long _b(_v);
        while (pwr) {
          if (pwr & 1) (res *= _b) %= _mod;
          (_b *= _b) %= _mod;
          pwr /= 2;
        }
        return res;
      }
      modint inv() const {
        assert(_v != 0);
        return pow(_mod - 2);
      }
  };
};
// ----------------------------------------------------------------------------------------

using mint = CMM::modint;

vector<int> g[200010];
#define SEG_ROOT 0,0,n
int sz[200010];
int a[200010]; // 1e9
vector<int> aa; // sort a
int da[200010]; // 离散化
void dfs(int u,int f){
  sz[u] = 1;
  rep(i,0,g[u].size()) if(g[u][i] == f) {
    swap(g[u][i],g[u].back());
    g[u].pop_back();
    break;
  }
  rep(i,0,g[u].size()){
    int v=g[u][i];
    dfs(v,u);
    sz[u] += sz[v];
    if(sz[g[u][i]] > sz[g[u][0]]) swap(g[u][0],g[u][i]);
  }
}

mint ans = 0;
const ll inv2 = mint(2).inv().val();
struct node{
  mint s2=0;
  mint sa2=0;
  mint lazymul=1;
  ll l=-1;
  ll r=-1;
};
int n;
struct SEGTREE{
  vector<node> seg; // 动态开点线段树, {sum 2^-len, a*2^-len,lazymul}
  void init(){
    seg = {node()};
  };
SEGTREE(){
  init();
}
void mul(int o,mint val){
  if(o==-1) return ;
  seg[o].s2 *= val;
  seg[o].sa2 *= val;
  seg[o].lazymul *= val;
}
void down(int o){
  mul(seg[o].l,seg[o].lazymul);
  mul(seg[o].r,seg[o].lazymul);
  seg[o].lazymul = 1;
}
pair<mint,mint> up(const pair<mint,mint>&n0,const pair<mint,mint>&n1) {
  return pair<mint,mint>{ n0.first + n1.first, n0.second + n1.second, };
}
pair<mint,mint> query(int o,int l,int r,int ql,int qr){
  if(o==-1) return {0,0};
  // printf("l,r = %d %d, ql,qr => %d %d\n",l,r,ql,qr);
  if(ql <= l and r <= qr) return {seg[o].s2,seg[o].sa2};
  if(ql >= r or r <= l) return {0,0};
  down(o);
  return up(query(seg[o].l,l,mid,ql,qr),query(seg[o].r,mid,r,ql,qr));
}
pair<mint,mint> query(int ql,int qr){
  return query(SEG_ROOT,ql,qr);
}
void add(int o,int l,int r,int p,pair<mint,mint> val){
  if(l+1==r){
    seg[o].s2+=val.first;
    seg[o].sa2+=val.second;
    return ;
  }
  down(o);
  if(p < mid) {
    if(seg[o].l == -1) {
      seg[o].l = seg.size();
      seg.push_back(node());
    }
    add(seg[o].l,l,mid,p,val);
  }else{
    if(seg[o].r == -1) {
      seg[o].r = seg.size();
      seg.push_back(node());
    }
    add(seg[o].r,mid,r,p,val);
  }
  seg[o].s2  = (seg[o].l!=-1?seg[seg[o].l].s2 :mint(0)) + (seg[o].r!=-1?seg[seg[o].r].s2 :mint(0));
  seg[o].sa2 = (seg[o].l!=-1?seg[seg[o].l].sa2:mint(0)) + (seg[o].r!=-1?seg[seg[o].r].sa2:mint(0));
}
void add(int p,pair<mint,mint> val){
  add(SEG_ROOT,p,val);
}
void dumps(int o,int l,int r,vector<tuple<ll,mint,mint> >&res){
  if(o == -1) return ;
  if(l+1==r){
    if(seg[o].s2 !=0 or seg[o].sa2 != 0) res.push_back({l,seg[o].s2,seg[o].sa2});
    return ;
  }
  down(o);
  dumps(seg[o].l,l,mid,res);
  dumps(seg[o].r,mid,r,res);
}
vector<tuple<ll,mint,mint> > vals(){
  vector<tuple<ll,mint,mint> > res;
  dumps(SEG_ROOT,res);
  return res;
}

} tn[200010];
int off=0; // 增加复用
void solve(int u,int pos/*减少交换*/){
  auto addcost = [&](ll idx,mint _s2){
    {
      auto [s2,sa2] = tn[pos].query(0,idx); // [1,val)
      ans += _s2*s2*aa[idx];
      ans -= _s2*sa2;
    }
    {
      auto [s2,sa2] = tn[pos].query(idx,n); // [val,N+1)
      ans -= _s2*s2*aa[idx];
      ans += _s2*sa2;
    }
  };
  if(g[u].size() == 0){
    addcost(da[u],1);
    tn[pos].add(da[u],{1,a[u]});
  }
  rep(i,0,g[u].size()){
    if(i == 0){
      solve(g[u][i], pos);
      tn[pos].mul(0,inv2);
      addcost(da[u],1);
      tn[pos].add(da[u],{1,a[u]});
    }else{
      int chid=off++;
      solve(g[u][i], chid);
      auto arr = tn[chid].vals();
      tn[chid].init();
      off--;
      for(auto [idx,_s2,_sa2]: arr) addcost(idx, _s2*inv2);
      for(auto [idx,_s2,_sa2]: arr) tn[pos].add(idx, {_s2*inv2,_sa2*inv2});
    }
  }
}
int main(){
  n=read();
  rep(i,1,n) {
    int u=read()-1;
    int v=read()-1;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  rep(i,0,n) a[i]=read();
  rep(i,0,n) aa.push_back(a[i]);
  sort(begin(aa),end(aa));
  rep(i,0,n) da[i] = lower_bound(begin(aa),end(aa),a[i])-begin(aa);

  dfs(0,0);
  solve(0,off++);
  printf("%d\n",(ans*mint(2).pow(n)).val());
  return 0;
}

题解

点分治,

简单说, 原来的线性分治，常见的是取中点分成等长线段来做

而点分治，就是找重心，然后切割成多个连通块

没了

F - 超现实子序列

s_v = [v,v+1,v-1,v+2,v-2,v+3,v-3,v+4,v-4,...] 是一个v开头的无穷序列

给数组a

问a的最长的子序列，且是某个s_x的序列的前缀

范围

n 1e6

ai [1,1e6]

1s

256mb

我的思路

理解错题意了，以为是要也是s_x的子序列

所以nowcoder数据是真的弱，我前面B题也理解错了，但是AC了

总结

E 第一次遇到点分治，理解了感觉还是很自然的