咸鱼失去了梦想， 熟悉下普及数据结构
三种优先级组织一堆数据
其实都是所谓优先队列qwq
栈
//STL
stack<int>s;
while(!s.empty()) s.pop();
s.push(1), s.push(2), s.push(3);
while(!s.empty()) {
cout << s.top() << ' ';
s.pop();
}
//手工
int s[11] = {0}, tp = 0;
s[++tp]=1, s[++tp]=2, s[++tp]=3;
while(tp) cout << s[tp--] << ' ';
// OutPut:
// 3 2 1
队列
//STL
queue<int>q;
while(!q.empty()) q.pop();
q.push(1), q.push(2), q.push(3);
while(!q.empty()) {
cout << q.front() << ' ';
q.pop();
}
//手工
int q[10]={0}, hd=1, tl=0;
q[++tl]=1, q[++tl]=2, q[++tl]=3;
while(hd<=tl) cout << q[hd++] << ' ';
// OutPut:
// 1 2 3
堆
//只实现小根堆
//统一定义节点
struct node{
int x,y;
bool operator<(const node& b)const {
// 用于priority_queue<node, vector<node>, less<node> >q;
// 大根堆
return y<b.y;
}
bool operator>(const node& b)const {
// 用于priority_queue<node, vector<node>, greater<node> >q;
// 小根堆
return y>b.y;
}
};
//STL
//--in the main()--
priority_queue<node, vector<node>, greater<node> >q;
q.push((node){0,3}), q.push((node){0,2}), q.push((node){0,1});
while(!q.empty()) {
printf("%d %d
", q.top().x, q.top().y);
q.pop();
}
-------------------
//暂时不想写可并堆qwq
-------------------
// OutPut:
/*
0 1
0 2
0 3
*/
序列上区间信息维护
ST表
维护区间 (最大/最小) 值（当然不止整数）， (O(nlog_2 n) - O(1))， 很稳。
这是一个维护区间最大整数的代码
int st[maxn][21]; // st[i][k] = min(a[i ~ i+(1<<k)-1]);
int ques(int l,int r)
{
int k=log2(r-l+1);
return max(st[l][k],st[r-(1<<k)+1][k]);
}
//------in the main()------
// 初始化 st[1~n][0]
for(int k=1;k<21;++k)
for(int i=1;i+(1<<k)-1<=n;++i)
st[i][k]=max(st[i][k-1],st[i+(1<<(k-1))][k-1]);
//-------------------------
树状数组
可以在有单点修改的情况下维护前缀可加且可减性信息， 在这点的基础上有很多扩展。（比如维护区间信息， 带区间修改的情况下维护区间信息）
luogu板子
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+15;
int n, t[maxn];
int lowb(int x) {return x&(-x);}
void ins(int x,int k) {
for(;x<=n;x+=lowb(x)) t[x] += k;
}
int qu(int x) {
int res=0; for(;x>0;x-=lowb(x)) res += t[x];
return res;
}
inline void p(int &x,int &y) {
printf("%d
", qu(y)-qu(x-1));
}
int main()
{
int m;
scanf("%d%d", &n,&m);
for(int i=0;i<n;++i) {
int a; scanf("%d", &a);
ins(i+1,a);
}
while(m--) {
int op,x,y; scanf("%d%d%d", &op, &x, &y);
(op==1) ? ins(x,y) : p(x,y);
}
return 0;
}
树状数组的一个trick
如果维护一个 “计数正整数集合” （此名为在下YY， 就是以 (cnt[i]) 表示 (i) 在集合中是否出现）， 还可以以 (O( log_2(集合size) )) 的复杂度找出集合中的第 (k) 大元素。
然后就可以写普通平衡树了
// 这是其中找第 k 大元素的代码
// 这种方法依托于树状数组的结构， 甚是巧妙
int kth(int k) {
int ans = 0, sum = 0;
// ans即要找的元素标号， sum表示 [1,ans] 有几个1
for (int i = log2(cnt) + 1; ~i; --i) {// ~i 等效于 i!=-1
if (ans + (1 << i) <= cnt && sum + t[ans + (1 << i)] < k)
sum += t[ans + (1 << i)], ans += 1 << i;
}
return ans + 1;
}
普通线段树
维护区间可加性信息， 似乎所有能用分治 (O(nlog_2n)) 统计的序列信息 都可以用线段树 (O(log_2n) - O(log_2n)) 维护。
线段树2
有助于理解线段树结构的题
//luogu 线段树2
#include<bits/stdc++.h>
using namespace std;
#define li long long
const int maxn = 1e5+15;
const int N = maxn<<3;
int n,m,p;
li a[maxn];
int rt, tot;
int sz[N], ch[N][2];
// size 儿子
li s[N], mt[N], at[N];
// sum 乘tag 加tag
inline void ud(int x) {
s[x]=(s[ch[x][0]]+s[ch[x][1]])%p;
}
inline void ml(int x, li k) {
s[x] = s[x]*k%p, mt[x]=mt[x]*k%p, at[x]=at[x]*k%p;
}
inline void ad(int x, li k) {
s[x] = (s[x]+k*sz[x]%p)%p, at[x]=(at[x]+k)%p;
}
inline void ps(int x) {
if(mt[x]!=1) {
ml(ch[x][0], mt[x]);
ml(ch[x][1], mt[x]);
mt[x]=1ll;
}
if(at[x]!=0) {
ad(ch[x][0], at[x]);
ad(ch[x][1], at[x]);
at[x]=0ll;
}
}
void build(int &x, int l, int r) {
x=++tot;
mt[x]=1;
if(l==r) {
s[x] = a[l];
sz[x] = 1;
return;
}
int mid = (l+r)>>1;
build(ch[x][0],l,mid);
build(ch[x][1],mid+1,r);
ud(x);
sz[x] = sz[ch[x][0]]+sz[ch[x][1]];
}
void mul(int x,int l,int r,int i,int j,li k) {
if(i<=l&&r<=j) {
ml(x,k);
return;
}
ps(x);
int mid=(l+r)>>1;
if(i<=mid) mul(ch[x][0],l,mid,i,j,k);
if(j >mid) mul(ch[x][1],mid+1,r,i,j,k);
ud(x);
}
void add(int x,int l,int r,int i,int j,li k) {
if(i<=l&&r<=j) {
ad(x,k);
return;
}
ps(x);
int mid=(l+r)>>1;
if(i<=mid) add(ch[x][0],l,mid,i,j,k);
if(j >mid) add(ch[x][1],mid+1,r,i,j,k);
ud(x);
}
li qs(int x,int l,int r,int i,int j) {
if(i<=l&&r<=j) return s[x];
ps(x);
int mid=(l+r)>>1;
li res = 0ll;
if(i<=mid) res+=qs(ch[x][0],l,mid,i,j), res%=p;
if(j >mid) res+=qs(ch[x][1],mid+1,r,i,j), res%=p;
return res;
}
int main()
{
scanf("%d%d%d", &n,&m,&p);
for(int i=1;i<=n;++i) scanf("%lld", &a[i]);
build(rt,1,n);
register int op,x,y;
register li k;
while(m--)
{
scanf("%d%d%d", &op,&x,&y);
if(op!=3) scanf("%lld", &k);
switch(op) {
case 1: mul(rt,1,n,x,y,k);
break;
case 2: add(rt,1,n,x,y,k);
break;
case 3: printf("%lld
", qs(rt,1,n,x,y));
break;
}
}
return 0;
}
zkw线段树（我还没学啊qwq）
李超线段树（我还没学啊qwq）