珂朵莉树ODT(基于std::set的暴力玄学数据结构)

news/2024/4/25 19:29:28

使一整段区间内的东西变得一样,数据随机。

在具有区间赋值操作,区间统计操作,以及最好保证数据随机的情况下在时空复杂度上把线段树吊起来打。

珂朵莉树的各种操作的总体复杂度始终为O(NlogN),这会吊打某些常数大、附加工作会影响总体复杂度的线段树算法。

typedef bool type;struct Node	//每个结点代表一个闭区间
{unsigned int l;unsigned int r;mutable type data;	//当前区间统一的类型和数值,data需要mutable修饰,这样可以在set中利用迭代器修改它Node(unsigned int a, unsigned int b = 0, type c = 0);	//定义构造函数bool operator <(const Node &a) const	//由于使用set来存储Node,所以需要重载小于号,使其按照左端点排序{return l < a.l;}
};Node::Node(unsigned int a, unsigned int b, type c)	//构造函数
{l = a;r = b;data = c;
}set <Node> s;	//没有初始化的珂朵莉树void init()	//初始化珂朵莉树
{for (int i = 0; i < n; ++i)	//通过给定数据,向其中不断插入区间长度为1的区间来完成初始化{static type temp = 0;cin >> temp;s.insert(Node(i, i, temp));}s.insert(Node(n, n, 0));	//在末尾多插入一个点
}set <Node>::iterator split(unsigned int pos)	//分裂操作:将包含位置pos的区间[l, r]分裂成[l, pos - 1]和[pos, r],并返回后者的迭代器
{set <Node>::iterator it = s.lower_bound(Node(pos));	//利用lower_bound()函数在set中查到左端点位置>=pos的结点if (it != s.end() && it->l == pos)	//如果这个结点的左端点位置正是pos,那么无需分裂,直接返回return it;it--;	//如果不是,那么必然大于pos,则包含位置pos的结点是上一个结点,it--//暴力分裂unsigned int l = it->l, r = it->r;type data = it->data;s.erase(it);//插入s.insert(Node(l, pos - 1, data));return s.insert(Node(pos, r, data)).first;	//返回[pos, r]值的迭代器
}
/*
//此时如果想使用区间[l, r]中的数据
set <Node>::iterator it2 = split(r + 1), it1 = split(l);	//必须先声明it2再声明it1,否则根据split中的erase操作,迭代器it1可能会失效(因为it1所属的结点可能被删除了)
for (; it1 != it2; ++it1)
{//具体操作
}
*/void assign(unsigned int l, unsigned int r, type val)	//	区间赋值(既然一个区间内所有的值全都一样了,那么在珂朵莉树中这个区间就可以只用一个结点来表示)
{set <Node>::iterator it2 = split(r + 1), it1 = split(l);s.erase(it1, it2);	//这个区间里所有结点全被删除s.insert(Node(l, r, val));	//使用一个新的结点来代替return ;
}
//assign的区间长度在随机数据下的期望为 N/3
//assign在赋值之余还可以顺便做做区间统计之类的,视情况而定

例题:https://ac.nowcoder.com/acm/contest/30184/C

#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>	
#include <stack>
#include <vector>
#include <algorithm>
#include <set>
#include <bitset>
#include <unordered_set>
#include <memory.h>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>	#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define x first
#define y second
#define all(a) a.begin(), a.end()
//#define int long long#define bug(a) cout << a << " *bug1*" << endl
#define bugg(a, b) cout << a << " " << b << " *bug2*" << endl
#define buggg(a, b, c) cout << a << " " << b << " " << c << " *bug3*" << endlusing namespace std;typedef long long LL;
typedef pair<LL, LL> PLL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};const int N = 1e5 + 5, mod = 1e9 + 7, INF = 0x3f3f3f3f;typedef LL type;struct Node	//每个结点代表一个闭区间
{unsigned int l;unsigned int r;mutable type data;	//当前区间统一的类型和数值,data需要mutable修饰,这样可以在set中利用迭代器修改它Node(unsigned int a, unsigned int b = 0, type c = 0);	//定义构造函数bool operator <(const Node &a) const	//由于使用set来存储Node,所以需要重载小于号,使其按照左端点排序{return l < a.l;}
};Node::Node(unsigned int a, unsigned int b, type c)	//构造函数
{l = a;r = b;data = c;
}set <Node> s;	//没有初始化的珂朵莉树/*
void init()	//初始化珂朵莉树
{for (int i = 0; i < n; ++i)	//通过给定数据,向其中不断插入区间长度为1的区间来完成初始化{static type temp = 0;cin >> temp;s.insert(Node(i, i, temp));}s.insert(Node(n, n, 0));	//在末尾多插入一个点
}
*/set <Node>::iterator split(unsigned int pos)	//分裂操作:将包含位置pos的区间[l, r]分裂成[l, pos - 1]和[pos, r],并返回后者的迭代器
{set <Node>::iterator it = s.lower_bound(Node(pos));	//利用lower_bound()函数在set中查到左端点位置>=pos的结点if (it != s.end() && it->l == pos)	//如果这个结点的左端点位置正是pos,那么无需分裂,直接返回return it;it--;	//如果不是,那么必然大于pos,则包含位置pos的结点是上一个结点,it--//暴力分裂unsigned int l = it->l, r = it->r;type data = it->data;s.erase(it);//插入s.insert(Node(l, pos - 1, data));return s.insert(Node(pos, r, data)).first;	//返回[pos, r]值的迭代器
}
/*
//此时如果想使用区间[l, r]中的数据
set <Node>::iterator it2 = split(r + 1), it1 = split(l);	//必须先声明it2再声明it1,否则根据split中的erase操作,迭代器it1可能会失效(因为it1所属的结点可能被删除了)
for (; it1 != it2; ++it1)
{//具体操作
}
*/void assign(unsigned int l, unsigned int r, type val)	//	区间赋值(既然一个区间内所有的值全都一样了,那么在珂朵莉树中这个区间就可以只用一个结点来表示)
{set <Node>::iterator it2 = split(r + 1), it1 = split(l);s.erase(it1, it2);	//这个区间里所有结点全被删除s.insert(Node(l, r, val));	//使用一个新的结点来代替return ;
}
//assign的区间长度在随机数据下的期望为 N/3
//assign在赋值之余还可以顺便做做区间统计之类的,视情况而定LL querysum(unsigned int l, unsigned int r)
{LL res = 0;set <Node>::iterator it2 = split(r + 1), it1 = split(l);	//必须先声明it2再声明it1,否则根据split中的erase操作,迭代器it1可能会失效(因为it1所属的结点可能被删除了)for (; it1 != it2; ++it1)res += (it1->r - it1->l + 1) * it1->data;return res;
}LL solve(int l, int r)
{LL ans = 0;set <Node>::iterator it2 = split(r + 1), it1 = split(l);set <LL> temp;for (; it1 != it2; ++it1)temp.insert(it1->data);for (auto &it:temp)if (it != 0)ans++;return ans;
}int main()
{	int n, q, op, l, r;scanf("%d%d", &n, &q);s.insert(Node(1, n, 1));while (q--){scanf("%d%d%d", &op, &l, &r);if (op == 1)assign(l, r, 1);if (op == 2){LL temp = querysum(l, r);assign(l, r - 1, 0);assign(r, r, temp);}if (op == 3)printf("%lld\n", solve(l, r));}return 0;
}

https://www.xjx100.cn/news/663758.html

相关文章

DDR中的ODT

ODT电阻端接 ODT (on-die termination) 裸片终端&#xff08;ODT&#xff09;功能允许DRAM通过ODT控制引脚为x4 / x8配置的每个DQ&#xff0c;DQS / DQS&#xff0c;RDQS / RDQS和DM信号打开/关闭终端电阻。对于x16配置&#xff0c;ODT通过ODT控制引脚应用于每个DQ&#xff0…

java解析.odt文件

1、了解.odt文件 .odt文件是openoffice软件产生的文档格式&#xff0c;可以直接用office打开&#xff0c;这其实就是一个压缩包&#xff0c;可以使用解压软件打开&#xff0c;里面有一个content.xml文件&#xff0c;这个文件内有<text:p>标签&#xff0c;标签内就是展示出…

DDR中的一些知识点说明(ODT,ZQ校准,OCT,TDQS)

ODT ( On-DieTermination ,片内终结)ODT 也是 DDR2 相对于 DDR1 的关键技术突破,所谓的终结(端接),就是让信号被电路的终端吸 收掉,而不会在电路上形成反射, 造成对后面信号的影响。 顾名思义, ODT 就是将端接电阻移植 到了芯片内部,主板上不再有端接电路。在进入DD…

DDR3系列-ODT-差分电容-容性补偿

DDR3 之 ODT ODT 是 On Die Termination 的缩写&#xff0c;又叫片内端接&#xff0c;顾名思义&#xff0c;就是将外部端接电阻放在了芯片内部&#xff0c;这个功能只有在 DDR2 以上的数据信号才有&#xff0c;DDR没有ODT。 有了这个功能&#xff0c;原本需要在 PCB 板上加串阻…

JESD79-4 第5章 片上终结电阻ODT(5.1-5.3)

DDR4 SDRAM支持ODT功能&#xff0c;此功能可通过ODT引脚控制、写命令或模式寄存器设置默认阻值来调整x4与x8设备的DQ, DQS_t, DQS_c与DM_n信号的终结电阻&#xff0c;x8设备除了上述引脚还可通过MR1.A111调整TDQS_t, TDQS_c的终结电阻。对于x16设备&#xff0c;ODT功能适用于D…

【转】DDR3中的ODT

ODT是什么鬼&#xff1f;为什么要用ODT&#xff1f;在很多关于DDR3的博文和介绍中都没有将清楚。在查阅了很多资料并仔细阅读DDR3的官方标准&#xff08;JESD79-3A&#xff09;之后&#xff0c;总算有点了头绪&#xff0c;下面来整理整理。 1、首先ODT是什么&#xff1f; ODT…

DDR功能点 ODT ZQ校准

ODT 也是 DDR2 相对于 DDR1 的关键技术突破&#xff0c;所谓的终结&#xff08;端接&#xff09;&#xff0c;就是让信号被电路的终端吸收掉&#xff0c;而不会在电路上形成反射&#xff0c; 造成对后面信号的影响。 顾名思义&#xff0c; ODT 就是将端接电阻移植到了芯片内部&…

On Die Termination (ODT) DDR

信号反射 在数据线和芯片连接点阻抗不一样&#xff0c;产生电信号反射&#xff0c;成为噪声&#xff0c;在高速电路中影响很大。 如下图&#xff0c;BUS上有两个DRAM&#xff0c;一个接收信号&#xff0c;一个反射&#xff0c;反射的信号会影响接收的DRAM。主板有termination电…