首页 > 其他分享 >P5312 竞赛实验班 Sol

P5312 竞赛实验班 Sol

时间:2022-09-07 09:12:58浏览次数:67  
标签:ch cur int MAX 实验班 Sol read P5312 bit

调了半天发现数组开小了,维护前缀和第二维下标写错了。

看到异或容易想到 Trie 树。

那么考虑每一个操作如何进行。

第一个操作直接 Trie 上插入就好了。

第二个操作发现是区间求和。那么想到维护一个前缀和,对于 Trie 的更新也随之更新即可。

第三个操作是全局异或,直接记一个 \(xor\) 表示当前异或标记即可,插入的时候直接异或这个标记再插入就好了。

第四个操作是排序。

很容易想到排序会打乱前面三个操作的顺序。但是想一下,这个 Trie 本身 \(0\)/\(1\) 就代表了数的大小关系,即对于已经插入的部分显然已经有序。那么前面所有操作可以转化为对于一个序列,前半部分有序,后半部分无序,求区间和。

但是操作三会改变原来维护的前缀和啊?没关系,对于一个 \(xor\) 标记,如果当前位为 \(1\) 那么交换两个子树;否则形态不变。

二操作拆成两段前缀和就很好维护了。

一操作也就不需要进行插入操作了,只需要维护以下后面无序部分的前缀和就可以了。

在这个意义上进行维护即可。

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

template <typename T> inline void read(T &x) {
  x = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar());
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return ;
}

const int N = 2e5 + 10, MAX = 31;
int n, m, Xor, tot = 1, ordered_n, a[N], tag[MAX];
int siz[N << 4], ch[N << 4][2], sum_u[N][MAX], sum_o[N << 4][MAX];

inline void ins(int x) {
  int cur = 1; ++siz[cur];
  for (int bit = 0; bit < MAX; ++bit) sum_o[cur][bit] += (x >> bit & 1);
  for (int i = MAX - 1; ~i; --i, ++siz[cur]) {
    int to = x >> i & 1;
    if (!ch[cur][to]) ch[cur][to] = ++tot; cur = ch[cur][to];
    for (int bit = 0; bit < MAX; ++bit) sum_o[cur][bit] += (x >> bit & 1);
  }
  return ;
}

inline ll query_o(int x) {
  int cur = 1; ll res = 0; int ex = 0;
  for (int i = MAX - 1; ~i; --i) {
    if (x <= siz[ch[cur][tag[i]]])
      cur = ch[cur][tag[i]], ex |= (tag[i] << i);
    else {
      x -= siz[ch[cur][tag[i]]]; int to = tag[i] ^ 1;
      for (int bit = 0; bit < MAX; ++bit) {
        int curans = sum_o[ch[cur][tag[i]]][bit];
        if (Xor >> bit & 1) curans = siz[ch[cur][tag[i]]] - curans;
        res += (ll)curans << bit;
      }
      cur = ch[cur][to], ex |= (to << i);
    }
  }
  return res + (ll)(Xor ^ ex) * x;
}

inline ll query_u(int l, int r) {
  ll res = 0;
  for (int i = 0; i < MAX; ++i) {
    int curans = sum_u[r][i] - sum_u[l - 1][i];
    if (Xor >> i & 1) curans = r - l + 1 - curans;
    res += (ll)curans * (1 << i);
  }
  return res;
}

inline ll query(int l, int r) {
  if (r <= ordered_n) return query_o(r) - query_o(l - 1);
  if (ordered_n < l) return query_u(l, r);
  return query_o(ordered_n) - query_o(l - 1) + query_u(ordered_n + 1, r);
}

inline void solve() {
  int opt, l, r, x; read(opt);
  if (opt == 1) {
    read(a[++n]), a[n] ^= Xor;
    for (int bit = 0; bit < MAX; ++bit)
      sum_u[n][bit] = sum_u[n - 1][bit] + (a[n] >> bit & 1);
  } else if (opt == 2) {
    read(l), read(r); printf("%lld\n", query(l, r));
  } else if (opt == 3) {
    read(x), Xor ^= x;
  } else {
    for (int i = ordered_n + 1; i <= n; ++i) ins(a[i]);
    for (int bit = 0; bit < MAX; ++bit) tag[bit] = Xor >> bit & 1;
    ordered_n = n; for (int bit = 0; bit < MAX; ++bit) sum_u[n][bit] = 0;
  }
  return ;
}

int main() {
  read(n);
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
    for (int bit = 0; bit < MAX; ++bit)
      sum_u[i][bit] = sum_u[i - 1][bit] + (a[i] >> bit & 1);
  }
  read(m);
  while (m--) solve();
  return 0;
}

标签:ch,cur,int,MAX,实验班,Sol,read,P5312,bit
From: https://www.cnblogs.com/MistZero/p/P5312-Sol.html

相关文章

  • Typescript类型体操 - Absolute
    题目中文实现一个接收string,number或bigInt类型参数的Absolute类型,返回一个正数字符串。例如typeTest=-100;typeResult=Absolute<Test>;//expectedtobe"......
  • H3C 交换机重置console密码
    屋漏偏逢连夜雨、船迟又遇打头风,今天刚巧来机房调试网络,发现N年前的一台H3C交换机console口密码忘球了,这下脑子嗡嗡响,这可咋办嘞,总不能让业务这样等待下去吧,说干就干,谁让咱......
  • Elasticsearch和Solr的区别
    1、基于Lucene开发他们底层都是基于Lucene开发,使用了Lucene的倒排索引实现的2、解决IO阻塞性能solr在实时建立索引的时候产生的IO阻塞查询性能会比ES差一些3、是否......
  • "Search Solution Explorer" doesn't work properly in VS 2022
    "SearchSolutionExplorer"doesn'tworkproperlyinVS2022Thankyouforsharingyourfeedback!Therearetwothingsthatneedtobeclarified:Makesureyo......
  • ping: www.baidu.com: Temporary failure in name resolution
     001、问题root@PC1:/home/test3#pingwww.baidu.comping:www.baidu.com:Temporaryfailureinnameresolution  002、解决方法(修改DNS服务配置文件)vi......
  • P4587 神秘数 Sol
    主席树好题。本质上是对于前缀的理解与转化。同题见牛牛的凑数游戏。实际上那场比赛T2和T3都是前缀相关的题目。这题是T3,看到很容易想到二进制拆分。稍微推广一......
  • 去掉打包之后的console.log
    下载插件: npmibabel-plugin-transform-remove-console--save-dev在babel.config.js文件中添加: constprodPlugins=[]if(process.env.NODE_ENV==='produc......
  • React.js VS Solid.js,作为初学者,你应该学习哪个?
    React.jsVSSolid.js,作为初学者,你应该学习哪个?作为初学者,哪个框架对您的开发之旅最有帮助?作为第一次接触javascript前端框架的初学者,您可能想知道一些事情,例如,哪个最......
  • React.js VS Solid.js,作为初学者,你应该学习哪个?
    React.jsVSSolid.js,作为初学者,你应该学习哪个?作为初学者,哪个框架对您的开发之旅最有帮助?作为第一次接触javascript前端框架的初学者,您可能想知道一些事情,例如,哪个最......
  • 引入版本问题 spring-cloud版本:Finchley.RC1 和 spring-boot版本:2.0.4.RELEASE No
    springcloud和springboot引入版本问题spring-cloud版本:Finchley.RC1spring-boot版本:2.0.4.RELEASE改为:spring-cloud版本:Finchley.RELEASEspring-boot版本:2.0.3.R......