Educational Codeforces Round 23 E. Choosing The Commander (trie)

题目链接: Educational Codeforces Round 23 E. Choosing The Commander

题意:

一共有n个操作。

1.  插入一个数p

2.  删除一个数p

3.  询问有多少个数 使得 x^p<l

题解:

对于前两种操作用01trie就能解决。

对于对三个操作,我们考虑在trie上搜索。

1.  当l的bit位是1时,那边bit位是p的字数全部的数都会小于l,(因为p^p=0)

2.  当l的bit为是0时,那边只能向bit位是p的子树中搜。

这样算下来 三种操作的时间复杂度都为log(1e8)。总复杂度为nlog(1e8)

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4
 5 const int N=2e6+7;
 6 int n,tr[N][2],cnt[N],ed=1,type,p,l;
 7
 8 void add(int x,int v)
 9 {
10     int now=1;
11     for(int i=30;i>=0;i--)
12     {
13         int tp=bool(x&(1<<i));
14         if(!tr[now][tp])tr[now][tp]=++ed;
15         cnt[now]+=v,now=tr[now][tp];
16     }
17     cnt[now]+=v;
18 }
19
20 int ask(int p,int l,int now=1,int bit=30)
21 {
22     if(!now||bit<0)return 0;
23     int pp=bool(p&(1<<bit));
24     if(l&(1<<bit))return cnt[tr[now][pp]]+ask(p,l,tr[now][pp^1],bit-1);
25     else return ask(p,l,tr[now][pp],bit-1);
26 }
27
28 int main(){
29     scanf("%d",&n);
30     while(n--)
31     {
32         scanf("%d%d",&type,&p);
33         if(type==1)add(p,1);
34         else if(type==2)add(p,-1);
35         else scanf("%d",&l),printf("%d\n",ask(p,l));
36     }
37     return 0;
38 }

时间: 06-20

Educational Codeforces Round 23 E. Choosing The Commander (trie)的相关文章

Educational Codeforces Round 23 F. MEX Queries(线段树)

题目链接:Educational Codeforces Round 23 F. MEX Queries 题意: 一共有n个操作. 1.  将[l,r]区间的数标记为1. 2.  将[l,r]区间的数标记为0. 3.  将[l,r]区间取反. 对每个操作,输出标记为0的最小正整数. 题解: hash后,用线段树xjb标记一下就行了. 1 #include<bits/stdc++.h> 2 #define ls l,m,rt<<1 3 #define rs m+1,r,rt<&l

Educational Codeforces Round 23 D. Imbalanced Array(单调栈)

题目链接:Educational Codeforces Round 23 D. Imbalanced Array 题意: 给你n个数,定义一个区间的不平衡因子为该区间最大值-最小值. 然后问你这n个数所有的区间的不平衡因子和 题解: 对每一个数算贡献,a[i]的贡献为 当a[i]为最大值时的 a[i]*(i-l+1)*(r-i+1) - 当a[i]为最小值时的a[i]*(i-l+1)*(r-i+1). 计算a[i]的l和r时,用单调栈维护.具体看代码,模拟一下就知道了. 然后把所有的贡献加起来.

Educational Codeforces Round 21 G. Anthem of Berland(dp+kmp)

题目链接:Educational Codeforces Round 21 G. Anthem of Berland 题意: 给你两个字符串,第一个字符串包含问号,问号可以变成任意字符串. 问你第一个字符串最多包含多少个第二个字符串. 题解: 考虑dp[i][j],表示当前考虑到第一个串的第i位,已经匹配到第二个字符串的第j位. 这样的话复杂度为26*n*m*O(fail). fail可以用kmp进行预处理,将26个字母全部处理出来,这样复杂度就变成了26*n*m. 状态转移看代码(就是一个kmp

Educational Codeforces Round 26 D. Round Subset(dp)

题目链接:Educational Codeforces Round 26 D. Round Subset 题意: 给你n个数,让你选其中的k个数,使得这k个数的乘积的末尾的0的个数最大. 题解: 显然,末尾乘积0的个数和因子2和因子5的个数有关. 然后考虑dp[i][j]表示选i个数,当前因子5的个数为j时,能得到因子2最多的为多少. 那么对于每个数,记录一下因子2和5的个数,做一些01背包就行了. 1 #include<bits/stdc++.h> 2 #define mst(a,b) me

Educational Codeforces Round 25 F. String Compression(kmp+dp)

题目链接:Educational Codeforces Round 25 F. String Compression 题意: 给你一个字符串,让你压缩,问压缩后最小的长度是多少. 压缩的形式为x(...)x(...)  x表示(...)这个出现的次数. 题解: 考虑dp[i]表示前i个字符压缩后的最小长度. 转移方程解释看代码,这里要用到kmp来找最小的循环节. 当然还有一种找循环节的方式就是预处理lcp,然后通过枚举循环节的方式. 这里我用的kmp找的循环节.复杂度严格n2. 1 #inclu

Educational Codeforces Round 22 E. Army Creation(主席树)

题目链接:Educational Codeforces Round 22 E. Army Creation 题意: 给你n个数和一个数k,然后有q个询问. 每个询问 有一个区间[l,r],问你这个区间内在满足每一种数不超过k的情况下,最大能选多少个数出来. 强制在线. 题解: 一看就要用到主席树,和主席数求区间内有多少不同的数的个数处理方法相同. 依次将每个数插入,当这个数出现的个数等于k了,就把最前面的那个数删掉. 然后询问就访问root[r]就行了. 第一次写完数据结构没有调试一遍过样例,一

Educational Codeforces Round 21 D. Array Division

题目链接:Educational Codeforces Round 21 D. Array Division 题意: 给你n个数,现在你可以改变1<=个数的位置,然后问你是否存在有一个k,使得sum(a[i])(1<=i<=k)==sum(a[j])(k+1<=j<=n) 题解: 分析: 如果需要将一个数移动,无非就是将这个数从第一部分移到第二部分,或者从第二部分移到第一部分. 所以,我们只需要开两个map来记录一下两部分有哪些数. 当两部分的差值/2等于其中一部分的一个数时

CodeForces 837F - Prefix Sums | Educational Codeforces Round 26

按tutorial打的我血崩,死活挂第四组- - 思路来自FXXL /* CodeForces 837F - Prefix Sums [ 二分,组合数 ] | Educational Codeforces Round 26 题意: 设定数组 y = f(x) 使得 y[i] = sum(x[j]) (0 <= j < i) 求初始数组 A0 经过多少次 f(x) 后 会有一个元素 大于 k 分析: 考虑 A0 = {1, 0, 0, 0} A1 = {1, 1, 1, 1} -> {C(

Educational Codeforces Round 26 D dp,思维

Educational Codeforces Round 26 D. Round Subset 题意:有 n 个数,从中选出 k 个数,要使这 k 个数的乘积末尾的 0 的数量最多. tags:dp好题 dp[i][j][l] 表示前 i 个数,选取了其中 j 个数,分解因子后有 l 个 5时,最多有多少个 2 .i 这一维明显可以省略. 这题一开始有个地方写挫了..选取 j 个数时,应该反着来,即 for( j, k, 1) ,不是 for( j, 1, k) ,不然会多算. #include