首页 > 其他分享 >树状数组 好题整理

树状数组 好题整理

时间：2023-04-29 19:23:20浏览次数：44  
标签：树状 int 好题 long update 数组 include define

树状数组 好题整理

[SDOI2009] HH的项链

离线询问后，按右端点升序排序，考虑建立一个树状数组，只包含 0/1，把含每种颜色的点中最靠右的位置打上 1 的标记，询问 \([l, r]\) 答案即为 \(query_r - query_{l - 1}\)，可以证明，如果一个相同颜色的点的位置对答案有贡献，那么最靠右的位置也一定能作贡献。

Code 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define int long long
using namespace std;

const int N = 1e6 + 10;

int n, m;

struct BIT
{
	int tr[N];
	void update(int x, int v)
	{
		for(; x <= N - 10; x += (-x) & x)
			tr[x] += v;
	}
	
	int query(int x)
	{
		if(x == 0) return 0;
		int sum = 0;
		for(; x; x -= (-x) & x)
			sum += tr[x];
		return sum;
	}
	
	void clear() { memset(tr, 0, sizeof tr); }
} bit;

struct node
{
	int l, r, id;
	bool operator < (const node &W) const
	{
		return r < W.r;
	}
} a[N];

int p[N];

int to[N];
int ans[N];

signed main()
{
	n = read();
	for(int i = 1; i <= n; i ++)
		p[i] = read();
	
	m = read();
	
	for(int i = 1; i <= m; i ++)
		a[i] = {read(), read(), i};
	
	sort(a + 1, a + m + 1);
	
	int rr = 1;
	for(int i = 1; i <= m; i ++)
	{
		int id = a[i].id;
		while(rr <= a[i].r)
		{
			if(to[p[rr]]) bit.update(to[p[rr]], -1);
			bit.update(rr, 1);
			to[p[rr]] = rr;
			rr ++;
		}
		ans[id] = bit.query(a[i].r) - bit.query(a[i].l - 1);
	}
	
	for(int i = 1; i <= m; i ++)
		cout << ans[i] << '\n';
	
	return 0;
}

[HEOI2012]采花

与上一道题类似，只不过若颜色个数等于 1 也不计入贡献，那么我们只需要把贡献放到次靠右的位置上即可。

Code 
#include <algorithm>
#include <cstring>
#include <iostream>
#define speedup (ios::sync_with_stdio(0), cin.tie(0), cout.tie(0))
#define int long long
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e6 + 10;

int tr[N];
void update(int a, int b) 
{
	if(a <= 0) return ; 
	for(; a <= N - 5; a += (-a) & a) 
		tr[a] += b;
}
int query(int a) {int sum = 0; for(; a ; a -= a & (-a)) sum += tr[a]; return sum;}

int n, k, m;
int a[N];

int p[N][3];

struct Q
{
	int l, r, id;
	bool operator <(const Q &W) const { return r < W.r; }
} q[N];

int ans[N];

signed main()
{
	speedup;
	cin >> n >> k >> m;
	for(int i = 1; i <= n; i ++)
		cin >> a[i];
	
	for(int i = 1; i <= m; i ++)
		cin >> q[i].l >> q[i].r, q[i].id = i;
	
	sort(q + 1, q + m + 1);
	
	int now = 0;
	for(int i = 1; i <= m; i ++)
	{
		int r = q[i].r;
		while(now <= r)
		{
			update(p[a[now]][1], -1);
			update(p[a[now]][2], 1);
			p[a[now]][1] = p[a[now]][2];
			p[a[now]][2] = now;
			now ++;
		}
		
		ans[q[i].id] = query(q[i].r) - query(q[i].l - 1);
	}
	
	for(int i = 1; i <= m; i ++)
		cout << ans[i] << '\n';
		

    return 0;
}

[POI2015] LOG

可以发现，如果一个数大于等于 \(s\)，那么它肯定会被一直选中，设有 \(cnt\) 个数大于 \(s\)。

结论：若满足

\[(c - cnt)s \le\sum_{0 < p_i < s}p_i \]

则这次询问有解，否则无解。

则需要维护：

  • 所有小于 \(s\) 的数的和
  • 所有大于等于 \(s\) 的数的数量

这都可以用树状数组做

Code 
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define int long long

using namespace std;

const int N = 2e6 + 10;

int n, m;
struct BIT
{
	int tr[N];
	void update(int a, int b)
	{
		for(; a <= m + 3; a += (-a) & a)
			tr[a] += b;
	}
	
	int query(int a)
	{
		int sum = 0;
		for(; a; a -= (-a) & a)
			sum += tr[a];
		return sum;
	}
} bit1, bit2;

struct Q
{
	int op, a, b;
} q[N];

int disc[N], idx;
int p[N], pp[N];

signed main()
{
	cin >> n >> m;
	
	for(int i = 1; i <= m; i ++)
	{
		char ch;
		int a, b;
		cin >> ch >> a >> b;
		q[i] = {ch == 'Z', a, b};
		disc[++ idx] = b;
		// 0 修改，1 查询 
	}
	
	sort(disc + 1, disc + idx + 1);
	idx = unique(disc + 1, disc + idx + 1) - disc - 1;
	
	for(int i = 1; i <= m; i ++)
	{
		int op = q[i].op, a = q[i].a, b = lower_bound(disc + 1, disc + idx + 1, q[i].b) - disc;
		if(op)
		{
			if(q[i].b * (a - (bit1.query(m + 1) - bit1.query(b - 1))) <= bit2.query(b - 1))
				puts("TAK");
			else
				puts("NIE");
		}
		else
		{
			if(p[a])
				bit1.update(pp[a], -1), bit2.update(pp[a], -p[a]);
				
			p[a] = q[i].b, pp[a] = b;
			bit1.update(b, 1);
			bit2.update(b, p[a]);
		}
	}
	
	return 0;
}

[JSOI2009] 计数问题

首先考虑一维问题如何解，只需要开 \(c\) 个树状数组，若一个位置上有该颜色就在对应的颜色树状数组上打上1。

二维的问题多加一维即可。

Code 
#include <algorithm>
#include <cstring>
#include <iostream>
#define speedup (ios::sync_with_stdio(0), cin.tie(0), cout.tie(0))
#define int long long
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e6 + 10;

int tr[N];
void update(int a, int b) 
{
	if(a <= 0) return ; 
	for(; a <= N - 5; a += (-a) & a) 
		tr[a] += b;
}
int query(int a) {int sum = 0; for(; a ; a -= a & (-a)) sum += tr[a]; return sum;}

int n, k, m;
int a[N];

int p[N][3];

struct Q
{
	int l, r, id;
	bool operator <(const Q &W) const { return r < W.r; }
} q[N];

int ans[N];

signed main()
{
	speedup;
	cin >> n >> k >> m;
	for(int i = 1; i <= n; i ++)
		cin >> a[i];
	
	for(int i = 1; i <= m; i ++)
		cin >> q[i].l >> q[i].r, q[i].id = i;
	
	sort(q + 1, q + m + 1);
	
	int now = 0;
	for(int i = 1; i <= m; i ++)
	{
		int r = q[i].r;
		while(now <= r)
		{
			update(p[a[now]][1], -1);
			update(p[a[now]][2], 1);
			p[a[now]][1] = p[a[now]][2];
			p[a[now]][2] = now;
			now ++;
		}
		
		ans[q[i].id] = query(q[i].r) - query(q[i].l - 1);
	}
	
	for(int i = 1; i <= m; i ++)
		cout << ans[i] << '\n';
		

    return 0;
}

[POI2015] LOG

可以发现，如果一个数大于等于 \(s\)，那么它肯定会被一直选中，设有 \(cnt\) 个数大于 \(s\)。

结论：若满足

\[(c - cnt)s \le\sum_{0 < p_i < s}p_i \]

则这次询问有解，否则无解。

则需要维护：

  • 所有小于 \(s\) 的数的和
  • 所有大于等于 \(s\) 的数的数量

这都可以用树状数组做

Code 
#include <algorithm>
#include <cstring>
#include <iostream>
#define speedup (ios::sync_with_stdio(0), cin.tie(0), cout.tie(0))
#define int long long
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 3e2 + 10, M = 110;

int n, m;
int a[N][N];
int tr[N][N][M];

void update(int x, int y, int c, int v)
{
	for(int i = x; i <= n + 1; i += (-i) & i) 
	    for(int j = y; j <= m + 1; j += (-j) & j)
		    tr[i][j][c] += v;
}

int query(int x, int y, int c)
{
	int sum = 0;
	for(int i = x; i; i -= i & (-i))
    	for(int j = y; j; j -= j & (-j))    
    		sum += tr[i][j][c];
	return sum;
}

int Query(int x1, int x2, int y1, int y2, int c)
{
	return query(x2, y2, c) - query(x1 - 1, y2, c) - query(x2, y1 - 1, c) + query(x1 - 1, y1 - 1, c);
}

signed main()
{
	speedup;
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++)	
			cin >> a[i][j], update(i, j, a[i][j], 1);
	int T;
	cin >> T;
	while(T --)
	{
		int op, x1, x2, y1, y2, c;
		cin >> op;
		if(op == 1)
		{
			cin >> x1 >> y1 >> c;
			update(x1, y1, a[x1][y1], -1);
			a[x1][y1] = c;
			update(x1, y1, c, 1);
		}
		else
		{
			cin >> x1 >> x2 >> y1 >> y2 >> c;
			cout << Query(x1, x2, y1, y2, c) << '\n';
		}
	}
    return 0;
}

[NOIP2017 提高组] 列队

\(70\%\)：

前 \(50\%\) 离散化询问就好了。

剩下的可以用 01 树状数组做，若一个数未被删除就打上 1 否则为 0，然后在树状数组上二分出要删除的位置，这样就可以在 \(O(\log^2 n)\) 内删除元素并插入至末尾。

\(100\%\) 咕咕咕

标签：树状,int,好题,long,update,数组,include,define
From： https://www.cnblogs.com/MoyouSayuki/p/17364384.html

相关文章

  • react的类组件和函数组件 -- 状态 state
    //函数组件是无状态的既没有数据的类似vue组件中的data数据//类组件是有状态的组件是有数据的是双向绑定的数据是数据驱动视图的负责UI的视图更新（单个组件的私有数据组件之间的数据是独立的）importReactDomfrom"react-dom"import{Component}from"react......
  • 数组模拟实现数据结构
    数组模拟链表实现①单链表:邻接表(存储图和树)②双链表:优化某些问题单链表inte[N]存储val,intne[N]存储next//单链表模板inthead,e[N],ne[N],idx;//head表示头节点的下标,e[i]表示节点i的值,ne[i]表示节点i的指针是多少,idx存储当前已经用到了哪个点v......
  • 力扣---1493. 删掉一个元素以后全为 1 的最长子数组
    给你一个二进制数组 nums ，你需要从中删掉一个元素。请你在删掉元素的结果数组中，返回最长的且只包含1的非空子数组的长度。如果不存在这样的子数组，请返回0。 提示1：输入：nums=[1,1,0,1]输出：3解释：删掉位置2的数后，[1,1,1]包含3个1。示例2：输入：nums=[0,1,1,1,0......
  • 第三章-栈 队列和数组
    栈stack数据接口三要素逻辑,运算,存储只允许在一端进行数据插入和删除操作.LIFO规则,lastinfirstout先进后出联想到烤串.doge卡特兰数(catalan),n个不同元素进栈,出栈元素不同排列的个数为顺序栈链栈只在头结点插入和删除就是链栈队列FIFOfirstinfirsto......
  • 数组和字符串
    数组操作读取数组中的元素，是通过访问索引的方式来读取的，一般从0位置开始。对于数组，计算机在内存中为其申请一段连续的空间，且会记下索引为0处的内存地址。主要的四种操作为：读取，查找，插入和删除元素。1.寻找数组的中心索引：给定整数数组nums，计算数组的中心下标（其左侧所有元素相......
  • 023 指针数组和数组指针
     /*一:原理二:指针数组三:数组指针*/ 一:原理定义变量:intnum=1;1组合:符号+名称(1)符号:数据类型(2)名称:要操作的数据类型(3)符号为名称所服务的。2优先:(1)默认优先级(2)离符号近(从......
  • 有序数组（类模板）
    一、问题描述：实现一个类模板，它可以接受一组数据，能对数据排序，也能输出数组的内容。每行输入的第一个数字为0，1，2或3:为0时表示输入结束；为1时表示将输入整数，为2时表示将输入有一位小数的浮点数，为3时表示输入字符。如果第一个数字非0，则接下来将输入一个正整数，表示即将输入的数据的......
  • JPA 使用@query 时，判断数组
    一般如果使用@query时，我们的sql是这样的：select*fromtwhere(ifnull(:a,'')=''ort.a=:a)and(ifnull(:b,'')=''ort.b=:b)但如果a参数是一个数组a=[1,2,3]，怎么办？ifnull会变成ifnull(1,2,3,'')=''这时我们可以使用  COALESCE(:a)isnu......
  • go语言 数组和切片、可变长参数、maps、字符串、指针、结构体、方法、接口
    数组和切片数组#1定义，初始化，使用#2数组是值类型数字，字符串，布尔，数组，都是值类型，真正直接存数据切片，map，指针引用类型，是个地址，指向了具体的值#3数组长度#4循环打印数组#5多纬数组#6数组定义并赋初值,把第99赋值为1，其他都是0#数组的长度也......
  • 将字节数组输入流拷贝成字节数组输出流，将ByteArrayInputStream转成ByteArrayOutputStr
    /**将ByteArrayInputStream拷贝成ByteArrayOutputStream*将字节数组输入流拷贝成字节数组输出流*/publicstaticByteArrayOutputStreamgetByteArrayOutputStream(ByteArrayInputStreaminputStream)throwsIOException{ByteArrayOutpu......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99