【GDOI2019模拟2019.3.25】芬威克树_alan_cty的博客-程序员秘密

技术标签: 树状数组  GDOI2019模拟  芬威克树  数据结构  位运算  

Description

在这里插入图片描述给出一段伪代码,其中lowbit(x)表示x在k进制下最低非零位的值,你需要维护这样一个东西,支持这两种操作。
x<=10^9 q,k<=200000

Solution

首先每个点x+lowbit(x)唯一,所以所有的点形成了一棵树
问题变成了链修改单点求
考虑当k为奇数时,所有的操作不会改变x的最低非0位
即所有的点形成了以 ( 2 x + 1 ) k d , ( 2 x + 1 &lt; k , d &gt; = 0 ) (2x+1)k^d,(2x+1&lt;k,d&gt;=0) (2x+1)kd,(2x+1<k,d>=0)开头的一堆链,如果能对每个数找到它所在的开头就做完了
当k为偶数时,考虑将k写成 k = 2 p ∗ a k=2^p*a k=2pa,a是奇数,那么可以发现所有的 S = 2 q ∗ b S=2^q*b S=2qb,b是奇数且q>=b的S也形成了一堆以 ( 2 x + 1 ) ∗ 2 p k d , ( ( 2 x + 1 ) 2 p &lt; k , d &gt; = 0 ) (2x+1)*2^pk^d,((2x+1)2^p&lt;k,d&gt;=0) (2x+1)2pkd,((2x+1)2p<k,d>=0)开头的链
对于剩下的点,我们考虑暴力跳到第一个合法的S
注意到对于一个x,如果最低位不变那么只需要跳p次就跳到了,否则就说明有进位产生,而进位最多为 log ⁡ k n \log_kn logkn次,所以总次数为 p ∗ log ⁡ k n = log ⁡ 2 k ∗ log ⁡ k n = log ⁡ 2 n p*\log_kn=\log_2k*\log_kn=\log_2n plogkn=log2klogkn=log2n
现在问题就变成了对于一个数找到其对应的开头,考虑最低位不会改变,所以会一直/2直到不能再除,然后就会产生退位
总的退位次数我们是可以计算出来的,对于数x,其最低位为t,那么退位次数为 ⌊ x k t ⌋ \lfloor {x\over k^t}\rfloor ktx,直接倍增求出来就行了
复杂度大概是 O ( q log ⁡ k n log ⁡ 2 n ) O(q\log_kn\log_2n) O(qlogknlog2n),由于当k=2时有点跑不过所以特判了。。。。

Code

#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

int read() {
    
	char ch;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	int x=ch-'0';
	for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

void write(int x) {
    
	if (!x) {
    puts("0");return;}
	char ch[20];int tot=0;
	for(;x;x/=10) ch[++tot]=x%10+'0';
	fd(i,tot,1) putchar(ch[i]);
	puts("");
}

const int N=2e5+5,M=N<<5;

int tr[M],ls[M],rs[M],tot,rt[M];

void modify(int &v,int l,int r,int x,int y) {
    
	if (!v) v=++tot;tr[v]^=y;
	if (l==r) return;
	int mid=l+r>>1;
	if (x<=mid) modify(ls[v],l,mid,x,y);
	else modify(rs[v],mid+1,r,x,y);
}

int query(int v,int l,int r,int x,int y) {
    
	if (!v) return 0;
	if (x<=l&&r<=y) return tr[v];
	int mid=l+r>>1,tmp=0;
	if (x<=mid) tmp^=query(ls[v],l,mid,x,y);
	if (y>mid) tmp^=query(rs[v],mid+1,r,x,y);
	return tmp;
}

int n,q,k,l,p,w,cnt,pw[35],ct[N],g[N][35];
int inv[N];

map<int,int> Id,Val;

int low(int x) {
    int d=1;for(;!(x%k);x/=k) d++;return d;}
int lowbit(int x) {
    int d=1;for(;!(x%k);x/=k) d++;return pw[d-1]*(x%k);}
int Lowbit(int x) {
    for(;!(x%k);x/=k);return x%k;}

int find(int x) {
    
	int t=low(x),s=Lowbit(x),d=t==w?0:x/pw[t];
	fd(j,30,1)
		while ((1<<j)-1<=d) {
    
			d-=(1<<j)-1;
			s=g[s][j];
		}
	s=g[s][0];
	return Id[s*pw[t-1]];
}

void Modify(int x,int v) {
    
	for(;ct[Lowbit(x)]<p&&x<=n;x+=lowbit(x)) Val[x]^=v;
	if (x>n) return;
	int pos=find(x);
	modify(rt[pos],1,n,x,v);
}

int Query(int x) {
    
	if (ct[Lowbit(x)]<p) return Val[x];
	int pos=find(x);
	return query(rt[pos],1,n,1,x);
}

int main() {
    
	freopen("fenwick.in","r",stdin);
	freopen("fenwick.out","w",stdout);
	n=read();q=read();k=read();
	if (k==2) {
    
		for(;q;q--) {
    
			int opt=read(),x=read();
			if (opt==1) modify(rt[0],1,n,x,read());
			if (opt==2) write(query(rt[0],1,n,1,x));
		}
		return 0;
	}
	for(l=k;!(l&1);l>>=1) p++;
	for(int x=n;x;x/=k) w++;
	pw[0]=1;fo(i,1,w-1) pw[i]=pw[i-1]*k;
	fo(i,1,w)
		fo(j,0,k/2-1) {
    
			int x=(2*j+1)*(1<<p);
			if (x>=k||x*pw[i-1]>n) break;
			Id[x*pw[i-1]]=++cnt;
			for(int y=x;y<k;y*=2) g[y][0]=x;
		}
	fo(i,1,k) for(int x=i;!(x&1);x>>=1) ct[i]++;
	fo(i,1,k) if (ct[i]>=p) inv[i*2%k]=i;
	fo(j,1,30) fo(i,1,k) g[i][j]=g[inv[g[i][j-1]]][j-1];
	for(;q;q--) {
    
		int opt=read(),x=read();
		if (opt==1) {
    
			int v=read();
			Modify(x,v);
		}
		if (opt==2) {
    
			int ans=0;
			for(;x;x-=lowbit(x)) ans^=Query(x);
			write(ans);
		}
	}
	return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/alan_cty/article/details/88808227

智能推荐

VIVADO 4.CDMA的使用_馍加馒头的博客-程序员秘密

本次实验测试CDMA来在ddr与bram之间搬运数据。1.Vivado工程CDMA上同时连接了四个BRAM。Bram设置为BRAM Controller模式,真双口BRAM,宽度64,深度1024,这样分配地址8k即可。2.地址分配(要注意)3.SDK代码#include "xparameters.h"#include ...

单链表及其基本操作_.sunshine的博客-程序员秘密

单链表的基本操作数据结构在代码优化以及设计过程的地位不可忽视,数据结构里包含很多内容,后续会一 一附上。此骗博客主要谈单链表,主要从其定义及创建,再完成一个简单的归并练习进行描述:单链表的定义 在链表存储中,每个节点不仅包含所存元素的信息,还包含元素之间逻辑关系的信息。这么说有点抽象,我们可以这么理解:单链表中前驱结点包含后继结点的地址信息,这样就可以通过前驱结点中的地址信息来寻找后继结点的位置

断开和连接mysql_mysql连接和断开_只有三分钟的赛雷的博客-程序员秘密

连接和断开服务器连接连接服务器,你通常需要有mysql用户名和密码,如果服务器在另外一台机器,你需要一个host名字,可以联系你的管理员找到,如果是在本机,可以忽略host,默认为本机,一旦你得到正确的参数,你就可以连接了,象下面:shell&gt; mysql -h host -u user -pEnter password: ********以上的参数host,user分别代表你连接服务器的主...

你所不知道的程序员(程序猿、攻城狮)_代码工雨花石的博客-程序员秘密

恩,今天和大家来聊一聊程序员。现如今,程序员在中国的科技圈可以说已经达到了举足轻重的地步了,强大的腾讯帝国,强大的阿里帝国,他们哪一个不是有上万程序员堆起来的。没有他们,哪儿来的天猫、支付宝,哪来的在网上买买买;没有他们,哪来的微信、QQ, 哪来的在网上聊聊聊(yue yue yue)。当然,并不是说阿里或者腾讯的成功全是程序员的功劳,但至少,他们的功劳是应该排在第一位的。由此,可以窥见程...

全国省市区数据库sql_hurace的博客-程序员秘密

内容来源于网络,有部分自己的修改。/*SQLyog Ultimate v12.08 (64 bit)MySQL - 5.1.69 **********************************************************************//*!40101 SET NAMES utf8 */;create table `wb_region` (

堆排序(heapSort)[email protected]的博客-程序员秘密

堆可以分为大根堆和小根堆,是一个完全二叉树堆排序是根据堆结构设计的一种排序堆的分类:大根堆:每个结点的值都大于其左孩子和右孩子结点的值小根堆:每个结点的值都小于其左孩子和右孩子结点的值数组中某元素的父结点和左右孩子结点,比如已知索引为i的数,那么1)父结点索引:(i-1)/22)左孩子索引:2i+13)右孩子索引:2i+2堆排序算法思路:1.首先将数组构造成一个大根堆,堆结构的顶端值为整个数组的最大值2.将顶端的数与末尾的数交换,此时,末尾的数为最大值,剩余待排序数组个数为 size

随便推点

Unity2018导出Android工程并自行生成apk(总)_ivy_0709的博客-程序员秘密_unity2018导出apk

所用版本unity2018.4.19打包流程:使用unity的gradle导出工程,在导出的工程中添加androidstudio生成的库工程以及做其他的设置,使用gradle打包最终的apk。下面是在这个过程中遇到的一些问题进行记录。1.如果需要开启自定义的.gradle文件,要勾选Playersetting中android的custom gradle template:会自动生成一个mainTemplate.gradle 文件,然后对这个文件进行自定义的修改(适配后续需要添加的and.

开源学习 Rweka_blacklee123的博客-程序员秘密

今天在找关联规则相关的资料时候,无意发现R语言中文论坛,虽然里面的资料有限,但是很有价值,譬如RWeka,一种开源的机器学习工具,在此予以介绍:背景介绍: #此前在首页部分显示#1)Weka:Weka有两种意思:一种不会飞的鸟的名字,一个机器学习开源项目的简称(Waikato Environment for Knowledge Analysis,http://www.cs.waikat

OKHTTP系列(九)---http请求头(header)作用_freak_csh的博客-程序员秘密_okhttp 头部

前言在项目开发中,网络请求是必不可少的 ,在http方面的知识学习也是不能拉下的,这里就做一波http请求头的记录。Header:请求头个别参数和描述Header 解释 示例 Accept 指定客户端能够接收的内容类型 Accept: text/plain, text/html,application/json Accept-Charset 浏览器...

vue 中多接口请求时 按顺序执行接口使用await async_huangminmin1001的博客-程序员秘密_vue先执行一个接口再执行一个接口

async getSelectOrg () { console.log('----1') return axiosPost('/api/uum/org/orglist', { accessToken: localStorage.token, option: true}).then(response =&gt; { this.options_...

【视觉-摄像机2】opencv 调用工业摄像机(GigE接口详细说明)_苏源流的博客-程序员秘密_gige接口如何连到电脑

Basler_acA1300-30gc 摄像机通过GigE接口ip地址实现相机与PC通信,一般情况摄像机的SDK是无用,opencv的VideoCapture类实现调用工业摄像机,你可以我先用摄像机自带的软件设计摄像机的参数,采集速度曝光分辨率等参数。然后直接调用即可。

PHP5.3.3安装文件说明文件翻译_liu0121的博客-程序员秘密

<br />安装PHP <br />     __________________________________________________________________ <br /><br />   目录 <br />   前言 <br />   1。一般安装注意事项 <br />   2。安装Windows系统 <br /><br />        Windows安装程序 <br />        手工安装步骤 <br />        ActiveScri

推荐文章

热门文章

相关标签