首页

# CF242E XOR on Segment (线段树 + 拆位)

传送门， 某谷传送门

# 题意

<img src="https://z3.ax1x.com/2021/08/05/fecyy4.png" width="500px">

# 思路

aia_i 是 1e6 的大小，可以拆成最多 20 位。

线段树每个节点开个 20 大小数组，numinum_i 表示这段区间内有多少个节点二进制第 ii 位是 1。

根据异或的性质，某一位 ii​ 异或 1 时直接线段树上某节点 numi=length−numinum_i = length - num_i​​ ，异或 0 时不变。

总共最多 20 位，复杂度还是 O(nlogn)O(nlogn)​ 的。

# 代码

不开 ll 见祖宗

#include <cstdio>
#include <iostream>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define root 1,n,1
#define mid (l+r)>>1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
using ll = long long; // 见祖宗 * 1
const int MAXN = 1e5 + 233;
struct node
{
  ll sum;
  int num[21]; //num [i] 表示这个区间内有多少个数二进制第 i 位是 1
  bool lazy[21]; // tag
} z[MAXN << 2];
int n, T, a[MAXN];
bool clr[21]; // 进行 modify 操作时，对题意中 x 的拆位存在这里
void update(int rt)
{
  z[rt].sum = z[rt<<1].sum + z[rt<<1|1].sum;
  int tmp = 0;
  rep (i, 1, 20) // 顺带更新 num
    z[rt].num[i] = z[rt<<1].num[i] + z[rt<<1|1].num[i];
}
void color2(int l, int r, int rt) // 注释跟下边 color 一样
{
  z[rt].sum = 0;
  rep (i, 1, 20)
  {
    if (z[rt >> 1].lazy[i])
    {
      z[rt].num[i] = (r - l + 1) - z[rt].num[i];
      z[rt].lazy[i] ^= 1;
    }
    z[rt].sum += (ll)z[rt].num[i] * (1 << (i - 1)); // 见祖宗 * 2 (强转)
  }
}
void pushcol(int l, int r, int rt) //pushdown 这里写得好丑 QAQ
{
  rep (i, 1, 20) // 只要有一位是 1 就需要 push，且 push 一次后直接 break（所以好丑 QAQ
    if (z[rt].lazy[i])
    {
      int m = mid;
      color2(lson);
      color2(rson);
      rep (j, 1, 20) // 清标记
        z[rt].lazy[j] = 0;
      update(rt);
      break;
    }
}
void build(int l, int r, int rt)
{
  if (l == r)
  {
    rep (i, 1, 20) // 拆位，最多 20 位
      if ((a[l] >> (i - 1)) & 1)
        z[rt].num[i] = 1;
    z[rt].sum = a[l];
    return;
  }
  int m = mid;
  build(lson);
  build(rson);
  update(rt);
}
void color(int l, int r, int rt)
{
  z[rt].sum = 0; // 置为 0 方便统计新的 sum
  rep (i, 1, 20)
  {
    if (clr[i]) // 这一位被异或 1
    {
      z[rt].num[i] = (r - l + 1) - z[rt].num[i]; // 异或 1, 所有 0 和 1 互换
      z[rt].lazy[i] ^= 1; // 打标记
    }
    z[rt].sum += (ll)z[rt].num[i] * (1 << (i - 1)); // 重新统计总和
  }
}
void modify(int l, int r, int rt, int nl, int nr)
{
  if (nl <= l && r <= nr)
  {
    color(l, r, rt);
    return;
  }
  pushcol(l, r, rt);
  int m = mid;
  if (nl <= m)
    modify(lson, nl, nr);
  if (m < nr)
    modify(rson, nl, nr);
  update(rt);
}
ll query(int l, int r, int rt, int nl, int nr)
{
  if (nl <= l && r <= nr)
  {
    return z[rt].sum;
  }
  pushcol(l, r, rt);
  int m = mid;
  ll tans = 0; // 见祖宗 * 3
  if (nl <= m)
    tans += query(lson, nl, nr);
  if (m < nr)
    tans += query(rson, nl, nr);
  return tans;
}
int main()
{
  //freopen("in.txt", "r", stdin);
  scanf("%d", &n);
  rep (i, 1, n)
    scanf("%d", &a[i]);
  scanf("%d", &T);
  build(root);
  int tp, ll, rr, xx;
  while (T--)
  {
    scanf("%d", &tp);
    if (tp == 1)
    {
      scanf("%d%d", &ll, &rr);
      printf("%lld\n", query(root, ll, rr));
    }
    if (tp == 2)
    {
      scanf("%d%d%d", &ll, &rr, &xx);
      rep (i, 1, 20)
        if ((xx >> (i - 1)) & 1)
          clr[i] = 1;
        else
          clr[i] = 0;
      modify(root, ll, rr);
    }
  }
  return 0;
}
# CF620E New Year Tree (线段树 + dfs 序 + 颜色状压)
传送门， 某谷传送门
# 题意
给出一棵 nn 个节点的树，根节点为 1。每个节点上有一种颜色 cic_i。mm 次操作。操作有两种：
  • 1 u c : 将以 uu 为根的子树上的所有节点的颜色改为 cc 。
  • 2 u : 查询以 uu 为根的子树上有多少种不同颜色。
数据范围： n, m 4e5. c <= 60.
# 思路
dfs 序建立线段树，对以 uu 为根的子树操作相当于线段树上对 dfn[u],dfn[u]+size[u]−1dfn[u], dfn[u] + size[u] - 1 这个区间操作（size 是以 uu 为根的子树大小）。
颜色最多 60 种可以用 long long 表示，颜色取并集直接按位或。
# 代码
因为常量 1 跟 1ll 不同又见祖宗了
#include <cstdio>
#include <iostream>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define root 1,n,1
#define mid (l+r)>>1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
using ll = long long;
const int MAXN = 4e5 + 233;
int n, clr[MAXN]; //clr [i] 是编号为 i 的节点的初始颜色
struct edge
{
  int to, ne;
} e[MAXN << 1];
int fr[MAXN], tmp;
int dfn[MAXN], rev[MAXN], sz[MAXN]; //sz 是子树大小，rev 相当于 dfn 的逆 (dfs 序为 i 的节点编号是 rev [i])，建树的时候取颜色会用。
struct tree
{
  ll clr; // 当前树上的颜色集
  ll lazy;
} z[MAXN << 2];
void add(int u, int v)
{
  e[++tmp].to = v;
  e[tmp].ne = fr[u];
  fr[u] = tmp;
}
void dfs(int np)
{
  dfn[np] = ++tmp;
  rev[tmp] = np;
  sz[np] = 1;
  for (int k = fr[np]; k; k = e[k].ne)
  {
    int tp = e[k].to;
    if (dfn[tp]) continue;
    dfs(tp);
    sz[np] += sz[tp];
  }
}
int getnum(ll xx) // 二进制有几个 1 就相当于有几种不同颜色
{
  int tans = 0;
  while (xx)
  {
    if (xx & 1ll)
      tans++;
    xx >>= 1ll;
  }
  return tans;
}
void update(int rt)
{
  z[rt].clr = z[rt << 1].clr | z[rt << 1 | 1].clr;
}
void build(int l, int r, int rt)
{
  if (l == r)
  {
    z[rt].clr = (1ll << clr[rev[l]]); // 不写 ll 见祖宗，这里直接将颜色状压
    return;
  }
  int m = mid;
  build(lson);
  build(rson);
  update(rt);
}
void pushcol(int rt)
{
  if (z[rt].lazy)
  {
    z[rt << 1].clr = z[rt].lazy;
    z[rt << 1 | 1].clr = z[rt].lazy;
    z[rt << 1].lazy = z[rt].lazy;
    z[rt << 1 | 1].lazy = z[rt].lazy;
    z[rt].lazy = 0;
  }
}
void modify(int l, int r, int rt, int nl, int nr, ll v)
{
  if (nl <= l && r <= nr) // 普通的区间赋值操作
  {
    z[rt].clr = v;
    z[rt].lazy = v;
    return;
  }
  pushcol(rt);
  int m = mid;
  if (nl <= m)
    modify(lson, nl, nr, v);
  if (m < nr)
    modify(rson, nl, nr, v);
  update(rt);
}
ll query(int l, int r, int rt, int nl, int nr) // 查询出来的是个二进制表示的颜色集
{
  if (nl <= l && r <= nr)
  {
    return z[rt].clr;
  }
  pushcol(rt);
  int m = mid;
  ll tans = 0;
  if (nl <= m)
    tans |= query(lson, nl, nr);
  if (m < nr)
    tans |= query(rson, nl, nr);
  return tans;
}
int main()
{
  //freopen("in.txt", "r", stdin);
  int T;
  scanf("%d%d", &n, &T);
  rep (i, 1, n)
    scanf("%d", &clr[i]);
  int u, v;
  rep (i, 1, n - 1)
  {
    scanf("%d%d", &u, &v);
    add(u, v);
    add(v, u);
  }
  tmp = 0;
  dfs(1); // 找 dfs 序
  build(root);
  int type, xx, kk;
  while (T--)
  {
    scanf("%d", &type);
    if (type == 1)
    {
      scanf("%d%d", &xx, &kk);
      modify(root, dfn[xx], dfn[xx] + sz[xx] - 1, (1ll << kk));
    }
    else
    {
      scanf("%d", &xx);
      printf("%d\n", getnum(query(root, dfn[xx], dfn[xx] + sz[xx] - 1))); // 记得转换成颜色数
    }
  }
  return 0;
}
  
 更新于