首页 > 其他分享 >数据结构补充

数据结构补充

时间：2024-10-24 20:20:35浏览次数：1  
标签：__ include 补充 pos int while 数据结构 define

P1972 [SDOI2009] HH的项链

求[l,r]区间中颜色的数量

#include<cstdio>
#include<algorithm>
#include<vector>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
using namespace std;
const int N=1e6+5;
int c[N],ans,s;
int n,m,x,op,p[N],t[N],a[N],f[N],g[N];
int l[N],r[N];
vector<int> q[N],id[N];
int lowbit(int x){
	return x&(-x);
}
void add(int x,int y){
	x++;
	while (x<N) {
		c[x]+=y;
		x+=lowbit(x);
	}
}
int ask(int x){
	x++;
	s=0;
	while (x){
		s+=c[x];
		x-=lowbit(x);
	}
	return s;
}
int main(){
//	freopen("data.in","r",stdin);
	
	scanf("%d",&n);
	fo(i,1,n) scanf("%d",&a[i]);
	
	fo(i,1,n) {
		p[i]=t[a[i]];
		t[a[i]]=i;
	}

	scanf("%d",&m);
	fo(i,1,m){
		scanf("%d %d",&l[i],&r[i]);
		q[r[i]].push_back(l[i]-1);
		id[r[i]].push_back(i);
	}
	
	fo(i,1,n){
		add(p[i],1);
		f[i]=i;
//		printf("%d\n",f[i]);
		
		for (int j=0;j<(int)q[i].size();j++) {
			g[id[i][j]]=ask(q[i][j]);
		}
	}
	
	fo(i,1,m) {
		ans=g[i]-f[l[i]-1];
		printf("%d\n",ans);
	}
	return 0;
}

带修莫队

[国家集训队] 数颜色 / 维护队列

题目描述

墨墨购买了一套 \(N\) 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：

  1. \(Q\ L\ R\) 代表询问你从第 \(L\) 支画笔到第 \(R\) 支画笔中共有几种不同颜色的画笔。

  2. \(R\ P\ C\) 把第 \(P\) 支画笔替换为颜色 \(C\)。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
using namespace std;
const int N=1e6+5;
const int M=1e6+5;
int t,l[N],r[N],a[N],cnt[M],ans,n,m,pos[N],x,y;
int b[N],c[N],tot,z,d[N],e[N];
int o[N];
char op;
void R(int &x){
    int a=0;char c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-'0';
    x=a;
}
struct node{
	int l,r,t,id;
};
node q[N];
bool cmp(node a,node b){
	if (a.l/t!=b.l/t) return a.l/t<b.l/t;
	if (a.r/t!=b.r/t) return a.r/t<b.r/t;
	return a.t<b.t;
}
inline void del(int x){
	cnt[a[x]]--;
	if (!cnt[a[x]]) ans--;
}
inline void add(int x){
	cnt[a[x]]++;
	if (cnt[a[x]]==1) ans++;
}
int main(){
//	freopen("data.in","r",stdin);
	R(n); R(m);
	fo(i,1,n) R(a[i]);
	fo(i,1,n) e[i]=a[i];
	
	t=pow(n,1/3.0);
	t=t*t;
	
	tot=0;
	scanf("\n");
	fo(i,1,m) {
		scanf("%c %d %d\n",&op,&x,&y);
		
		if (op=='Q') {
	
			z++;
			q[z]=(node){x,y,tot,z};
		}
		else{
			tot++;
			b[tot]=x; 
			c[tot]=y;
			d[tot]=e[x];
			e[x]=y;
		}
	}
	
	sort(q+1,q+z+1,cmp);
	x=1; y=0; t=0; ans=0; 
	fo(i,1,z) {
		
		while (x<q[i].l) del(x++);
		while (y>q[i].r) del(y--);
		while (x>q[i].l) add(--x);
		while (y<q[i].r) add(++y);
		
		while (t<q[i].t) {
			t++;
			if (x<=b[t] && b[t]<=y) del(b[t]);
			a[b[t]]=c[t];
			if (x<=b[t] && b[t]<=y) add(b[t]);
		}
		
		while (t>q[i].t) {
			if (x<=b[t] && b[t]<=y) del(b[t]);
			a[b[t]]=d[t];
			if (x<=b[t] && b[t]<=y) add(b[t]);
			t--;
		}
		o[q[i].id]=ans;
	}
	fo(i,1,z) printf("%d\n",o[i]);
	return 0;
}

cdq分治

三维偏序

#include<bits/stdc++.h>
#define fo(i,a,b) for (register int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (register int (i)=(b);(i)>=(a);(i)--)
#define eb emplace_back
#define pi pair<ll,ll>
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc ((o<<1)|1)
#define A puts("Yes")
#define B puts("No")
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double db;
const ll mo1=1e9+7;
const ll mo2=1e9+9;
const ll P=131;
const ll Q=13331;
const ll mo=998244353;
const int N=2e5+5;
int c[N],n,k,cnt[N];
ll f[N];

struct node{
	int x,y,z,cnt,ans;
};
node a[N],b[N];
bool operator == (const node &a,const node &b){
	return a.x==b.x && a.y==b.y && a.z==b.z;

}
bool cmp1(node a,node b){
	if (a.x!=b.x) return a.x<b.x;
	if (a.y!=b.y) return a.y<b.y;
	return a.z<b.z;
}
bool cmp2(node a,node b){
	if (a.y!=b.y) return a.y<b.y;
	return a.z<b.z;
}
int lowbit(int x){
	return x&(-x);
}
void upd(int x,int y){
	for (;x<N;x+=lowbit(x)) c[x]+=y;
}
int ask(int x){
	int s=0;
	for (;x;x-=lowbit(x)) s+=c[x];
	return s;
}
void solve(int l,int r){
	if (l==r) return;
	int m=(l+r)>>1;
	solve(l,m); solve(m+1,r);
	
	sort(a+l,a+m+1,cmp2);
	sort(a+m+1,a+r+1,cmp2);
	int i=l,j=m+1;
	
	while (j<=r) {
		while (i<=m && a[i].y<=a[j].y) {
			upd(a[i].z, a[i].cnt);
			i++;
		}
		a[j].ans+=ask(a[j].z);
		j++;
	}
	
	fo(j,l,i-1) upd(a[j].z,-a[j].cnt);
}
int main() {
//    freopen("data.in", "r", stdin);
//    freopen("data.out", "w", stdout);
//	
	scanf("%d %d",&n,&k);
	fo(i,1,n) scanf("%d %d %d",&b[i].x, &b[i].y, &b[i].z);
	sort(b+1,b+n+1,cmp1);
	
	int tot=0;
	for (int i=1,j;i<=n;i=j+1) {
		j=i;
		while (j<n && b[i]==b[j+1]) {
			j++;
		}
		a[++tot]=b[i];
		a[tot].cnt=j-i+1;
	}
	
	solve(1,tot);
	
	fo(i,1,tot) f[a[i].ans+a[i].cnt-1]+=a[i].cnt;
	fo(i,0,n-1) printf("%lld\n",f[i]);
	
    return 0;
    


}

回滚莫队

歴史の研究

题面翻译

题目描述

JOI 教授决定用如下的方法分析这些日记：

  • 选择日记中连续的几天 \([L,R]\) 作为分析的时间段；

  • 定义事件 \(A\) 的重要度 \(W_A\) 为 \(A\times T_A\)，其中 \(T_A\) 为该事件在区间 \([L,R]\) 中出现的次数。

现在，您需要帮助教授求出所有事件中重要度最大的事件是哪个，并输出其重要度。

#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 5;
int n, q;
int x[N], t[N], m;

struct Query {
  int l, r, id;
} Q[N];

int pos[N], L[N], R[N], sz, tot;
int cnt[N], __cnt[N];
ll ans[N];

bool cmp(const Query& A, const Query& B) {
  if (pos[A.l] == pos[B.l]) return A.r < B.r;
  return pos[A.l] < pos[B.l];
}

void build() {
  sz = sqrt(n);
  tot = n / sz;
  for (int i = 1; i <= tot; i++) {
    L[i] = (i - 1) * sz + 1;
    R[i] = i * sz;
  }
  if (R[tot] < n) {
    ++tot;
    L[tot] = R[tot - 1] + 1;
    R[tot] = n;
  }
}

void Add(int v, ll& Ans) {
  ++cnt[v];
  Ans = max(Ans, 1LL * cnt[v] * t[v]);
}

void Del(int v) { --cnt[v]; }

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) cin >> x[i], t[++m] = x[i];
  for (int i = 1; i <= q; i++) cin >> Q[i].l >> Q[i].r, Q[i].id = i;

  build();

  // 对询问进行排序
  for (int i = 1; i <= tot; i++)
    for (int j = L[i]; j <= R[i]; j++) pos[j] = i;
  sort(Q + 1, Q + 1 + q, cmp);

  // 离散化
  sort(t + 1, t + 1 + m);
  m = unique(t + 1, t + 1 + m) - (t + 1);
  for (int i = 1; i <= n; i++) x[i] = lower_bound(t + 1, t + 1 + m, x[i]) - t;

  int l = 1, r = 0, last_block = 0, __l;
  ll Ans = 0, tmp;
  for (int i = 1; i <= q; i++) {
    // 询问的左右端点同属于一个块则暴力扫描回答
    if (pos[Q[i].l] == pos[Q[i].r]) {
      for (int j = Q[i].l; j <= Q[i].r; j++) ++__cnt[x[j]];
      for (int j = Q[i].l; j <= Q[i].r; j++)
        ans[Q[i].id] = max(ans[Q[i].id], 1LL * t[x[j]] * __cnt[x[j]]);
      for (int j = Q[i].l; j <= Q[i].r; j++) --__cnt[x[j]];
      continue;
    }

    // 访问到了新的块则重新初始化莫队区间
    if (pos[Q[i].l] != last_block) {
      while (r > R[pos[Q[i].l]]) Del(x[r]), --r;
      while (l < R[pos[Q[i].l]] + 1) Del(x[l]), ++l;
      Ans = 0;
      last_block = pos[Q[i].l];
    }

    // 扩展右端点
    while (r < Q[i].r) ++r, Add(x[r], Ans);
    __l = l;
    tmp = Ans;

    // 扩展左端点
    while (__l > Q[i].l) --__l, Add(x[__l], tmp);
    ans[Q[i].id] = tmp;

    // 回滚
    while (__l < l) Del(x[__l]), ++__l;
  }
  for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
  return 0;
}

标签：__,include,补充,pos,int,while,数据结构,define
From： https://www.cnblogs.com/ganking/p/18500405

相关文章

  • 新高一暑假第一期集训恢复性训练【数据结构-线段树晚测】(补)
    新高一暑假第一期集训恢复性训练【数据结构-线段树晚测】(补)A.[CF1045G]AIrobots我们先按视野降序排序，这样一个一个考虑，如果后面的能看到前面，那前面的也肯定能看到后面。这样，就是对于每一个机器人，在他前面有几个智商在\([q-k,q+k]\)，位置在\([x-r,x+r]\)。那么把这个东......
  • 【数据结构与算法】之栈详解
    栈（Stack）是一种基本的线性数据结构，遵循后进先出、先进后出的原则。本文将更详细地介绍栈的概念、特点、Java实现以及应用场景。1.栈概念概述想象一摞叠放的盘子，你只能从最上面取盘子，放盘子也只能放在最上面。栈就像这样一摞盘子，它只有一个开口，称为栈顶(Top)。另一端封闭，称......
  • 【数据结构与算法】之队列详解
    队列（Queue）是一种重要的线性数据结构，遵循先进先出、后进后出的原则。本文将更详细地介绍队列的概念、特点、Java实现以及应用场景。模运算小复习：a%b的值总是小于b5%4=1  5 %2=11%5=1  4%5=41.队列概念概述想象一下排队买票，先排队的人总是先买......
  • 大二上 数据结构与算法笔记 20241024
    一.inline在C和C++编程语言中，inline关键字是一种函数修饰符，用于建议编译器在编译时将函数的代码直接插入到每个函数调用的地方，而不是进行常规的函数调用。这样做的目的是减少函数调用的开销，尤其是在函数体较小且调用频繁的情况下。作用和优点：减少函数调用开销：通过将函数......
  • 数据结构与算法——双链表的实现
    上次学习了单链表，这次来学习双链表。二者之间的区别是，单链表中的每个结点只存有后继结点的地址，而双链表中则存了两个地址，一个是前驱结点的地址，一个是后继结点的地址。结构体structListNode{ intelement;//数据域 structListNode*next; ......
  • 数据结构懒标记时间戳差异问题
    对于数据结构打lazytag后节点时空不统一问题的解决可以看看之前写的一篇文章线段树初步理解，里头初步介绍了懒标记的作用与使用懒标记所带来的时空不统一的问题。实际上是可以将懒标记拓展到其他数据结构上的。就以经典的毛毛虫链剖分举例子，就是现在我要给树上的与给定......
  • 【C++篇】栈的层叠与队列的流动：在 STL 的韵律中探寻数据结构的优雅之舞
    文章目录C++栈与队列详解：基础与进阶应用前言第一章：栈的介绍与使用1.1栈的介绍1.2栈的使用1.2.1最小栈1.2.2示例与输出1.3栈的模拟实现第二章：队列的介绍与使用2.1队列的介绍2.2队列的使用2.2.1示例与输出2.3队列的模拟实现2.3.1示例与输出第三章：优先队......
  • 第十三章_数据结构与集合源码二
    目录8.Map接口分析8.1哈希表的物理结构8.2HashMap中数据添加过程8.2.1JDK7中过程分析8.2.2JDK8中过程分析8.3HashMap源码剖析8.3.1JDK1.7.0_07中源码1、Entry2、属性3、构造器4、put()方法8.3.2JDK1.8.0_271中源码1、Node2、属性3、构造器4、put()方法......
  • 【数据结构】-数组
    数组特点：数组的地址连续，可以通过下标获取数据。1.数组扩容步骤：$1.创建一个比原来数组更长的新数组$2.让原来数组当中的数据依次复制到新数组当中$3.让arr指向新数组，原数组空间释放  2.数组插入2.1最后位置插入$1.判断数组当中有没有位置，用size记录当......
  • 新高一暑假第一期集训恢复性训练【数据结构-晚测】（并查集）（补）
    新高一暑假第一期集训恢复性训练【数据结构-晚测】（并查集）（补）[CF1290C]PrefixEnlightment带权扩展域并查集。任意三个子集的交集为空集，显然，一个点最多只能在两个集合中出现，这样所有集合的大小之和是\(\Theta(n)\)的。一个在两个集合中出现的点ii相当于连接了\(2\)个集合......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99