H 华华和月月种树
链接：https://ac.nowcoder.com/acm/contest/392/H
思路：先得到整棵树最终的形态，在这棵树上进行三种操作，用dfs跑下，第二种操作就直接对最终形态树上这个点子树区间操作，第一种操作的时候是新加一个点，此时我们将那个点的权值设为0就好了，最后单点查询。。，很简单的数据结构题。
实现代码：
#include<bits/stdc++.h>
using namespace std;
const int M = 4e5+;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mid int m = (l + r) >> 1
vector<int>g[M];
int sum[M<<],lazy[M<<],a[M],b[M],cnt,head[M],in[M],out[M];
int tot,op[M]; void dfs(int u,int fa){
in[u] = ++tot;
for(int i = ;i < g[u].size();i++){
int v = g[u][i];
if(v != fa)
dfs(v,u);
}
out[u] = tot;
} void pushdown(int l,int r,int rt){
if(lazy[rt]){
mid;
lazy[rt<<] += lazy[rt];
lazy[rt<<|] += lazy[rt];
sum[rt<<] += lazy[rt]*(m-l+);
sum[rt<<|] += lazy[rt]*(r-m);
lazy[rt] = ;
}
} void update(int L,int R,int c,int l,int r,int rt){
if(L <= l&&R >= r){
sum[rt] += (r-l+)*c;
lazy[rt] += c;
return ;
}
pushdown(l,r,rt);
mid;
if(L <= m) update(L,R,c,lson);
if(R > m) update(L,R,c,rson);
} void update1(int p,int c,int l,int r,int rt){
if(l == r){
sum[rt] = ;
return;
}
pushdown(l,r,rt);
mid;
if(p <= m) update1(p,c,lson);
else update1(p,c,rson);
} int query(int p,int l,int r,int rt){
if(l == r){
return sum[rt];
}
pushdown(l,r,rt);
mid;
if(p <= m) return query(p,lson);
else return query(p,rson);
} int main()
{
ios::sync_with_stdio();
cin.tie(); cout.tie();
int n;
cin>>n;
int cnc = ;
for(int i = ;i <= n;i ++){
cin>>op[i]>>a[i]; a[i] ++;
if(op[i] == ){
cnc ++; b[i]= cnc;
g[a[i]].push_back(cnc);
g[cnc].push_back(a[i]);
}
else if(op[i] == ) cin>>b[i];
}
dfs(,);
for(int i = ;i <= n;i ++){
if(op[i] == ){
update(in[a[i]],out[a[i]],b[i],,tot,);
}
else if(op[i] == ){
update1(in[b[i]],,,tot,);
}
else{
cout<<query(in[a[i]],,tot,)<<endl;
}
}
return ;
}
F 华华开始学信息学
链接：https://ac.nowcoder.com/acm/contest/392/F
思路： 分块思维+bit， 和去年沈阳网络赛的J一样的思路，只不过那道是在树上的，这道相当于简化版，我们直接将D大小大于400的用bit暴力更新，小于400的用数组标记下就好了
实现代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 2e5+;
ll c[M],n,vis[M];
vector<ll>v;
void add(ll x,ll v){
while(x <= n){
c[x] += v;
x += (x&-x);
}
} ll getsum(ll x){
ll ret = ;
while(x){
ret += c[x];
x -= (x&-x);
}
return ret;
} int main()
{
ll m,x,op,y;
cin>>n>>m;
for(ll i = ;i <= m;i ++){
cin>>op>>x>>y;
if(op == ){
if(x <= ){
if(!vis[x])
v.push_back(x);
vis[x] += y;
}
else{
for(ll j = x;j <= n;j += x){
add(j,y);
}
}
}
else{
ll ans = ;
for(auto &k: v){
ans += (y/k - (x-)/k)*vis[k];
}
ans += getsum(y) - getsum(x-);
cout<<ans<<endl;
}
}
}
J 月月查华华的手机
链接：https://ac.nowcoder.com/acm/contest/392/J
思路：这道题范围给的很大，肯定不能用n*n的复杂度去写，最多只能 n*(logn), 因为子序列的字母之间是有先后关系的，我们先把母序列处理下，把每个字母的位置存到对应的vector里面，判断子序列时候合格时，我们遍历子序列每个字母，在当前字母对应的vector里二分取大于前一个字母位置的数，如果取不到那么这个子序列就不合格，如果取到了就保存下当前位置，继续遍历
实现代码：
#include<bits/stdc++.h>
using namespace std;
const int M = 1e6+;
vector<int>g[M];
int a[M];
int main()
{
string s,s1;
int n;
ios::sync_with_stdio();
cin.tie(); cout.tie();
cin>>s;
for(int i = ;i < s.size();i ++){
a[i] = s[i]-'a';
g[a[i]].push_back(i+);
}
cin>>n;
for(int i = ;i <= n;i ++){
cin>>s1;
int st = ,flag = ;
for(int j = ;j < s1.size();j ++){
int k = s1[j]-'a';
if(g[k].size()==){
flag = ;break;
}
int kk = upper_bound(g[k].begin(),g[k].end(),st) - g[k].begin();
if(kk >= g[k].size()){
flag = ;break;
}
st = g[k][kk];
}
if(!flag) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}