Hdu多校 @ Littlechai | 2021-07-24T20:20:28+08:00 | 4 分钟阅读 | 更新于 2021-07-24T20:20:28+08:00

Hdu多校补题

第二场

1002

题意

给出一颗树，支持下列两种操作

1 a b: 将a-b这条路径上的点<x1,x2,…,xn>分别加$1^2,2^2…n^2$

2 a: 查询点a的值

分析

首先考虑一条链的情况，对于连续区间l~r，一操作对于每个点的贡献是$(id[x]-id[l]+1)^2$，计$val=id[l]-1$拆开后$id[x]^2 - 2*id[x]*val + val^2$至此我萌就能用线段树维护了。

考虑树的情况，注意到在树上的区间是分割的，所以要动态维护L，R，x ~ lca上$val = id[l]-L$,lca ~ y上$val = id[l]+R$

  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

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) x&(-x)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
using namespace std;
const int maxn = 3e5+100;
int n, q;
int tot, dep[maxn], siz[maxn], id[maxn], fa[maxn], top[maxn], son[maxn];
vector<int>vec[maxn];
void dfs1(int x, int f){
     fa[x] = f;
     dep[x] = dep[f] + 1;
     siz[x] = 1;
     for(auto v: vec[x]){
          if(v == f) continue;
          dfs1(v, x);
          siz[x] += siz[v];
          if(siz[v] > siz[son[x]])
               son[x] = v;
     }
}
void dfs2(int x, int tp){
     id[x] = ++ tot;
     top[x] = tp;
     if(son[x]) dfs2(son[x], tp);
     for(auto v: vec[x]){
          if(v == fa[x] || v == son[x]) continue;
          dfs2(v, v);
     }
}

struct tree {
     ll sum[4];
     ll add[4];
}z[maxn*4];

void pushdown(int rt, int l, int r, int t){
     int mid = (l + r) >> 1;
     if(z[rt].add[t] != 0){
          ll k = z[rt].add[t];
          z[rt<<1].add[t] += k;
          z[rt<<1|1].add[t] += k;
          z[rt<<1].sum[t] += k*(mid-l+1);
          z[rt<<1|1].sum[t] += k*(r-mid);
          z[rt].add[t] = 0;
     }
}
void modify(int rt, int l, int r, int t, int nowl, int nowr, ll val){
     if(nowl <= l && r <= nowr){
          z[rt].sum[t] += val*(r-l+1);
          z[rt].add[t] += val;
          return ;
     }
     int mid = (l + r) >> 1;
     pushdown(rt, l, r, t);
     if(nowl <= mid) modify(lson, t, nowl, nowr, val);
     if(nowr > mid) modify(rson, t, nowl, nowr, val);
     z[rt].sum[t] = z[rt<<1].sum[t] + z[rt<<1|1].sum[t];
}


int getlca(int x, int y){
     for(;top[x] != top[y];){
          if(dep[top[x]] < dep[top[y]]) swap(x, y);
          x = fa[top[x]];
     }
     if(dep[x] > dep[y]) swap(x, y);
     return x;
}
void change(int x, int y){
//cout << "new change" << endl;
     int len = dep[x] + dep[y] - 2*dep[getlca(x, y)] + 1;
     int L = 1, R = len;
//cout << "L R " << L << " " << R << endl; 
     for(;top[x] != top[y];){
          if(dep[top[x]] > dep[top[y]]){
               ll val = id[top[x]] - L;
               modify(1, 1, n, 1, id[top[x]], id[x], 1);
               modify(1, 1, n, 2, id[top[x]], id[x], val);
               modify(1, 1, n, 3, id[top[x]], id[x], val*val);
               L += dep[x] - dep[top[x]] + 1;
               x = fa[top[x]];
          }
          else {
               ll val = id[top[y]] + R;
               modify(1, 1, n, 1, id[top[y]], id[y], 1);
               modify(1, 1, n, 2, id[top[y]], id[y], val);
               modify(1, 1, n, 3, id[top[y]], id[y], val*val);
               R -= dep[y] - dep[top[y]] + 1;
               y = fa[top[y]];
          }
     }
     if(dep[x] < dep[y]){
          ll val = id[x] - L;
          modify(1, 1, n, 1, id[x], id[y], 1);
          modify(1, 1, n, 2, id[x], id[y], val);
          modify(1, 1, n, 3, id[x], id[y], val*val);
     }
     else {
          ll val = id[y] + R;
          modify(1, 1, n, 1, id[y], id[x], 1);
          modify(1, 1, n, 2, id[y], id[x], val);
          modify(1, 1, n, 3, id[y], id[x], val*val);
     }
}
ll query(int rt, int l, int r, int t, int pos){
//cout << "query " << l << " " << r << " " << t << " " <<z[rt].sumendl;
     if(l == r){
          return z[rt].sum[t];
     }
     int mid = (l + r) >> 1;
     pushdown(rt, l, r, t);
     if(pos <= mid) return query(lson, t, pos);
     else return query(rson, t, pos);
}
int main(){
     scanf("%d",&n);
     for(int i = 1;i < n;i ++){
          int x, y;
          scanf("%d %d",&x,&y);
          vec[x].push_back(y);
          vec[y].push_back(x);
     }
     dfs1(1, 0);
     dfs2(1, 0);
     scanf("%d",&q);
     for(int i = 1;i <= q;i ++){
          int op, a, b, x;
          scanf("%d",&op);
          if(op == 1){
               scanf("%d %d",&a,&b);
               change(a, b);
          }
          if(op == 2){
               scanf("%d",&x);
               ll ans1 = query(1, 1, n, 1, id[x]);
               ll ans2 = query(1, 1, n, 2, id[x]);
               ll ans3 = query(1, 1, n, 3, id[x]);
               printf("%lld\n", ans1*id[x]*id[x] - 2*ans2*id[x] + ans3);
          }
     }
     return 0;
}

1004

题意

给出n个数，q组询问，每组询问l,r,a,b问l~r间满足$c \ xor \ a \le \ b$不同大小的$c$的数量

分析

对于不同大小的数量这种问题，很容易想到莫队，考虑用trie维护$c \ xor \ a \le \ b$就好了，然而这题超卡常（不会树套数的log做法

  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

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) x&(-x)
using namespace std;
const int maxn = 3e5+100;
int n, m;
int a[maxn], ans[maxn], cnt[maxn], size;
struct node {
     int l, r, a, b, id;
}q[maxn];
bool cmp(node x, node y){
     if(x.l/size == y.l/size) return x.r < y.r;
     else return x.l < y.l;
}

struct tree {
     int nxt[3], sum;
}z[maxn*10];
int tot = 1;

void re(int &x){
     x = 0;
     int b = 0;
     char ch = getchar();
     while(ch < '0' || ch > '9'){
          if(ch == '-') b = -1;
          ch = getchar();
     }
     while(ch >= '0' && ch <= '9'){
          x = (x << 1) + (x << 3) + ch - '0';
          ch = getchar();
     }
     if(b == -1)
          x *= -1;
}
void insert(int x, int v){
     int rt = 1;
     for(int i = 16;i >= 0;i --){
          z[rt].sum += v;
          int ch = (x>>i)&1;
          if(!z[rt].nxt[ch]){
               z[rt].nxt[ch] = ++ tot;
          }
          rt = z[rt].nxt[ch];
     }
     z[rt].sum += v;

}
void add(int x, int v){
     if(v == 1){
          if(!cnt[x]) insert(x, v);
          cnt[x] ++;
     }
     if(v == -1){
          cnt[x] --;
          if(!cnt[x]) insert(x, v);
     }
}
int query(int a, int b){
     int rt = 1, ans = 0;
     for(int i = 16;i >= 0;i --){


          if((a>>i)&1){
               if((b>>i)&1){
                    ans += z[z[rt].nxt[1]].sum;
                    rt = z[rt].nxt[0];
               }
               else rt = z[rt].nxt[1];
          }
          else {
               if((b>>i)&1){
                    ans += z[z[rt].nxt[0]].sum;
                    rt = z[rt].nxt[1];
               }
               else rt = z[rt].nxt[0];
          }
          // int ch = (a>>i)&1;
          // int cur = (b>>i)&1;

          // if(ch == 0 && cur == 0){
          //      rt = z[rt].nxt[0];
          // }
          // else if(ch == 0 && cur == 1){
          //      ans += z[z[rt].nxt[0]].sum;
          //      rt = z[rt].nxt[1];
          // }
          // else if(ch == 1 && cur == 0){
          //      rt = z[rt].nxt[1];
          // }
          // else if(ch == 1 && cur == 1){
          //      ans += z[z[rt].nxt[1]].sum;
          //      rt = z[rt].nxt[0];
          // }
     }
     ans += z[rt].sum;
     return ans;
}
int main(){

     //freopen("1.in","r",stdin);
     //freopen("wa.out","w",stdout);
     re(n);
     for(int i = 1;i <= n;i ++)
          re(a[i]);

     scanf("%d",&m);
     for(int i = 1;i <= m;i ++){
          re(q[i].l);re(q[i].r);re(q[i].a);re(q[i].b);
          q[i].id = i;
     }
     
     size = sqrt(n)+10;
     sort(q+1,q+1+m,cmp);

     int l = 1, r = 0;
     for(int i = 1;i <= m;i ++){
          int ql = q[i].l;
          int qr = q[i].r;
//cout << "new query " << ql << " " << qr << " " << q[i].a << " " << q[i].b << endl;
          while(l < ql) add(a[l ++], -1);
          while(l > ql) add(a[-- l], 1);
          while(r > qr) add(a[r --], -1);
          while(r < qr) add(a[++ r], 1);

          ans[q[i].id] = query(q[i].a, q[i].b);
     }
     for(int i = 1;i <= m;i ++){
          printf("%d\n",ans[i]);
     }
     return 0;
}

© 2021 - 2022 小柴Yeah

Powered by Hugo with theme Dream.

avatar

小柴YeahThe time is no time, when it is past

React