首页 > 其他分享 >树状数组题单记录

树状数组题单记录

时间：2024-06-02 15:14:17浏览次数：21  
标签：ch 树状 int long while num 数组 mx 题单

树状数组题单笔记

[SDOI2009] HH的项链

题目

思路

普通的 scanf 已经承受不住了，请使用关闭流同步的 cin 和 cout 或者经典快读

以下假设你已经使用了标准命名空间：

参考快读：

inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

参考关闭流同步：

ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

暴力很好想，直接枚举区间内部即可。

但是但看题目，这道题似乎没有修改，只有查询，那么它是怎么和树状数组扯上关系的呢？

先把查询区间按照左端点排个序，然后看样例：

6
1 2 3 4 3 5
3
1 2
3 5
2 6

看起来区间 3 到 5 中，出现了重复的 3，2 到 6 中也有。此时，我们可以忽略其中一个 3。如果按照左端点排序，我们就可以得到以下查询序列：

3
1 2
2 6
3 5

此时，很明显能看出来 2 到 6 区间是包含 3 到 5 区间的，此时，我们可以通过更换排序方式来进一步找方法，这次以右端点为关键字排序：

3
1 2
3 5
2 6

此时，如果我们在查询排完序后的第 2 和第 3 个区间时，我们就可以忽略掉第一个 3，进而只关注第二个 3，这样，我们就可以发现，按照右端点为关键字递增排序后，我们可以依次遍历区间更新某种贝壳是否存在，如果存在，就把它的位置更新掉，然后区间求和，复杂度能过 不是因为我不会证。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
inline int read(){
 int x=0,f=1;char ch=getchar();
 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
 while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
 return x*f;
}
class Binary_Tree{
 
 private:
 
 int t[N],n;
 
 int lowbit(int x){ return x & (-x) ; }
 
 public:
 
 void init(int x){ n = x ; }
 
 void add(int x,int y){
  while(x<=n){
   t[x]+=y;
   x+=lowbit(x);
  }
 }
 
 int sum(int x){
  int reu=0;
  while(x>0){
   reu+=t[x];
   x-=lowbit(x);
  }
  return reu;
 }
 
}t;
struct ques{
 int l,r;
 int xb;
};
int n,m;
int a[N],ans[N];
int pl[N];
vector <ques> pro;
bool cmp(ques a,ques b){ return a.r == b.r ? a.l > b.l : a.r < b.r ; }
signed main(){
 n=read();
 for(int i=1;i<=n;i++)
  a[i]=read();
 m=read();
 pro.reserve(m);
 t.init(n);
 for(int i=1;i<=m;i++)
  pro.push_back({read(),read(),i});
 sort(pro.begin(),pro.end(),cmp);
 int l=1;
 for(ques q:pro){
  for(int i=l;i<=q.r;i++){
   if(pl[a[i]])
    t.add(pl[a[i]],-1);
   t.add(i,1);
   pl[a[i]]=i;
  }
  l=q.r+1;
  ans[q.xb]=t.sum(q.r)-t.sum(q.l-1);
 }
 for(int i=1;i<=m;i++)
  cout<<ans[i]<<endl;
 return 0;
}

三元上升子序列

题目

思路

这道题有两个条件：

  1. \(A_i < A_j < A_k\)
  2. $ i < j < k$

乍一看很难。以下约定：

  1. 三个数字分别为 \(A\) \(B\) \(C\)。
  2. 这三个数字已经按照原题目默认顺序排好，即三个数字的位置以次递增其实不用排。

但是，如果我们从中间的数字 \(B\) 入手，条件就可以拆成：

  1. 在 \(B\) 前面且与 \(B\) 构成正序对的数量
  2. 在 \(B\) 后面且与 \(B\) 构成正序对的数量

这个问题就好解多了。然后，根据乘法定理可知结果为它俩相乘。

记得 #define int long long

Code

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
#define int long long
class Binary_Tree{
 
 private:
 
 int t[N];
 int n;
 
 int lowbit(int x){ return x & (-x) ; }
 
 public:
 
 void init(int x){ n = x ; }
 
 void add(int x,int y){
  while(x<=n){
   t[x]+=y;
   x+=lowbit(x);
  }
 }
 
 int sum(int x){
  int reu=0;
  while(x>0){
   reu+=t[x];
   x-=lowbit(x);
  }
  return reu;
 }
 
}tl,tr;
int n;
int a[N],l[N],r[N];
signed main(){
 cin>>n;
 tl.init(n);
 tr.init(n);
 vector <int> u;
 u.reserve(n);
 for(int i=1;i<=n;i++)
  cin>>a[i],u.push_back(a[i]);
  
 sort(u.begin(),u.end());
 auto end=unique(u.begin(),u.end());
 for(int i=1;i<=n;i++)
  a[i]=lower_bound(u.begin(),end,a[i])-u.begin()+1;
 
 int ans=0;
 for(int i=1;i<=n;i++){
  l[i]=tl.sum(a[i]-1);
  tl.add(a[i],1);
 }
 for(int i=n;i>=1;i--){
  tr.add(a[i],1);
  r[i]=n-i-tr.sum(a[i])+1;
 }
 for(int i=2;i<n;i++)
  ans+=l[i]*r[i];
 cout<<ans;
 return 0;
}

P3253 [JLOI2013] 删除物品

题目

思路

首先想一下模拟：

对于两个栈，由于每次删除只能删除当前优先度最大的物品 \(A\)，因此每次移动时就将 \(A\) 移动到另一个栈的顶端并使顺序反过来，然后删除 \(A\) 并寻找下一个 \(A\)。循环直到所有物品被删完。

代码：

纯手写的奇妙的支持查询和离散化的栈
十年 OI 一场空，不开 long long 见祖宗

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
#define int long long
inline int read(){
 int x=0,f=1;char ch=getchar();
 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
 while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
 return x*f;
}
class SpecialStack{
 
 private:
 
 int num[N];
 int topx,len;
 bool vis[N];
 
 public:
 
 inline void init(){
  topx=0 , len = 0;
  memset(vis,0,sizeof(vis));
 }
 inline void invis_push(int x,int i){
  topx = max(topx,i);
  num[i] = x ;
  len ++ ;
 }
 inline void push(int x){
  num[++topx] = x ;
  vis[num[topx]]=1;
  len ++ ;
 }
 inline int top(){ return num[topx] ; }
 inline void pop(){
  vis[num[topx]] = 0 , topx -- , len -- ;
 }
 inline void lsh(auto begin,auto end,int &mx){
  for(int i=1;i<=topx;i++){
   num[i]=lower_bound(begin,end,num[i])-begin+1;
   vis[num[i]]=1;
   mx=max(mx,num[i]);
  }
 }
 inline void clear(){ topx = len = 0 ; }
 inline bool find(int x){ return vis[x] ; }
 inline bool empty(){ return len ; }
}s1,s2;
int n1,n2;
int ans=0;
vector <int> l;
signed main(){
 cin>>n1>>n2;
 s1.init();
 s2.init();
 l.reserve(n1+n2);
 int num;
 for(int i=n1;i>=1;i--)
  s1.invis_push(num=read(),i),l.push_back(num);
 for(int i=n2;i>=1;i--)
  s2.invis_push(num=read(),i),l.push_back(num);
 sort(l.begin(),l.end());
 auto len=unique(l.begin(),l.end());
 int mx=0;
 int ans=0;
 s1.lsh(l.begin(),len,mx);
 s2.lsh(l.begin(),len,mx);
 while(mx)
  if(s1.find(mx)){
   while(s1.top()!=mx)
    s2.push(s1.top()),s1.pop(),ans++;
   s1.pop();
   mx--;
  }
  else{
   while(s2.top()!=mx)
    s1.push(s2.top()),s2.pop(),ans++;
   s2.pop();
   mx--;
  }
 cout<<ans;
 return 0;
}

然后你就会 T 掉一半的点。

现在我们来看一下两个栈之间来回交换物品的情况：

现在我们手造一组数据（从栈顶到栈底）：

3 3
1
2
3

4
5
6

两个栈的物品优先度分别为 1 2 3 和 4 5 6。现在我们要删除 6，看一下删除 6 之前两个栈的情况：

5 1
5
4
1
2
3

6

删除 6 之后，我们要删除 5，假如我们将 4 和 5 放回到原来的栈里：

3 2
1
2
3

4
5

可以发现，4 和 5 的相对位置没有变。

假设 4 5 我们已经删除掉了，现在我们只剩 1 2 3 需要删除：

3 0
1
2
3

3 在栈底，我们将 1 和 2 拿到另一个栈里：

1 2
3

2
1

现在可以直接依次删除 3 2 1 了。这个过程，我们很容易发现：数个物品一起在栈中来回拿的时候，它们的相对位置保持不变。因此，我们可以将两个栈的头相对接，使用一个变量来保存当前的头在哪里，就不用真的模拟来回移动物品的行为了。

那么这里和树状数组有什么关系呢？

删除掉一个物品时，我们要将这个物品的存在抹去，以防止对下次操作时计算步数产生影响。但是，如果每次删除物品都要把数据来回移动的话就和没有优化没什么区别。因此，我们可以使用树状数组进行单点修改（删除物品存在）和区间查询（统计所需步数）。

在开始时，先将所有物品添加到数组里，然后每删除一个就将它的存在抹去（加上 -1），此操作是 \(O(logN)\) 的，总时间复杂度是 \(O(NlogN)\) 的。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
#define int long long
inline int read(){
 int x=0,f=1;char ch=getchar();
 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
 while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
 return x*f;
}
struct node{
 int val,id;
}a[N];
bool cmp(node a,node b){ return a.val > b.val ; }
int ans=0;
int n1,n2,top,mx,n;
int t[N];
int lowbit(int x){ return x & (-x) ; }
void add(int x,int y){
 while(x<=n){
  t[x]+=y;
  x+=lowbit(x);
 }
}
int sum(int x){
 int reu=0;
 while(x){
  reu+=t[x];
  x-=lowbit(x);
 }
 return reu;
}
signed main(){
 cin>>n1>>n2;
 n=n1+n2;
 top=n1;
 for(int i=n1;i>=1;i--)
  a[i].val=read(),a[i].id=i,add(i,1);
 for(int i=n1+1;i<=n;i++)
  a[i].val=read(),a[i].id=i,add(i,1);
 sort(a+1,a+1+n,cmp);
 for(int i=1;i<=n;i++){
  mx=a[i].id;
  if(top<mx)
   ans+=sum(mx-1)-sum(top),top=mx-1,add(a[i].id,-1);
  else
   ans+=sum(top)-sum(mx),top=mx,add(a[i].id,-1);
 }
 cout<<ans;
 return 0;
}

P3660 [USACO17FEB] Why Did the Cow Cross the Road III G

题目

思路

题目条件很明显：

\(1~N\) 每个数字出现过两遍，第一次记为 \(a_i\)，第二次记为\(b_i\)，求 \(a_i<a_j<b_i<b_j\) 的对数，即求两个数构成的数对，其中数 \(i\) 每次出现的位置都比数 \(j\) 出现的位置早但是 \(i\) 第二次出现的位置比 \(j\) 第一次出现的位置晚，这样的数对的数量。

为什么题目不写翻译直接写题目要求的结果啊啊啊啊

首先，我们将输入的牛按照第一次出现的位置排序，这样从头遍历时就满足了 \(a_i<a_j\) 的条件。

然后我们来求 \(b_i<b_j\) 的数量。这里可以直接用树状数组来求，每次更新完后将第二次出现的位置累加进树状数组即可。

最后我们来满足 \(a_j<b_i\)。现在树状数组里的点都是前面已经遍历过的第二次出现的位置。我们只需要在答案里减去在当前牛第一次出现位置前面的位置即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=50005;
#define ipi pair <int,int> 
int t[N*2];
int n;
ipi pl[N];
bool cmp(ipi x,ipi y){ return x.first < y.first ; }
int lowbit(int x){ return x & (-x) ; }
void add(int x,int y){
 while(x<=n*2){
  t[x]+=y;
  x+=lowbit(x);
 }
}
int sum(int x){
 int reu=0;
 while(x>0){
  reu+=t[x];
  x-=lowbit(x);
 }
 return reu;
}
signed main(){
 cin>>n;
 int num;
 for(int i=1;i<=n;i++)
  pl[i].first=pl[i].second=0;
 for(int i=1;i<=n*2;i++){
  cin>>num;
  if(!pl[num].first)
   pl[num].first=i;
  else
   pl[num].second=i;
 }
 sort(pl+1,pl+1+n,cmp);
 int ans=0;
 for(int i=1;i<=n;i++){
  ans+=sum(pl[i].second)-sum(pl[i].first-1);
  add(pl[i].second,1);
 }
 cout<<ans;
 return 0;
}

标签：ch,树状,int,long,while,num,数组,mx,题单
From： https://www.cnblogs.com/CLydq-Blogs/p/18222120

相关文章

  • 每日刷题——相遇、宝石（模拟+数学）、相助（模拟+数组）、相依（dp的优化）
    相遇原题链接登录—专业IT笔试面试备考平台_牛客网题目描述运行代码#include<iostream>usingnamespacestd;intmain(){inta,b;cin>>a>>b;if(a==b){cout<<"p";}elseif(a-b==1||(a==1&&b==3)){cout<<&qu......
  • 数组的降序排序（Java）
    代码：importjava.util.*;publicclasssz{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);//定义数组长度System.out.println("请输入数组的长度：");intlength=scanner.nextInt();......
  • 02、数组
    1、数组概述数组是多个相同类型数据按一定顺序排列的集合，并使用一个名字命名，并通过编号的方式对这些数据进行统一管理数组本身是引用数据类型，而数组中的元素可以是任何数据类型，包括基本数据类型和引用数据类型创建数组对象会在内存中开辟一整块连续的空间，而数组名中引用的是......
  • Q3 LeetCode34 在排序数组中找起始位置
    提交错误：数组访问越界1.验证数组越界的语句要放在执行语句的前面，要不然前面报错无法进行到后面部分2.本题使用两次二分查找，左边界找到后，将rigiht指针设置成mid-1，继续查找更左的边界，右边界同理将left设置成mid+13.newint[]{1,1}  新数组创建方式 1classSolution{......
  • Shell阶段08 数组(普通数组, 关联数组), 示例(数组的遍历与循环)
    数组基本概述#shell的数组用的比较少，一般都用awk。因为shell的数组比awk慢很多什么是数组简单来说:数组其实就是变量的一种，变量只能存储一个值，而数组可以存储多个值数组的分类分为两类普通数组关联数组普通数组:只能使用正整数作为数组索引关联数组:可以使用......
  • Java数组
    Java数组1.数组概念数组的定义数组是相同类型数据的有序集合数组描述的是相同类型的若干个数据，按照一定的先后次序排列组合而成其中，每一个数据称作一个数组元素，每个数组元素可以通过一个下标来访问他们2.数组声明创建首先必须声明数组变量，才能在程序中使用数组。下面是......
  • 10.Golang中的数组
    1、Array(数组)的介绍数组是指一系列同一类型数据的集合。数组中包含的每个数据被称为数组元素(element)，这种类型可以是任意的原始类型，比如int、string等，也可以是用户自定义的类型。一个数组包含的元素个数被称为数组的长度。在Golang中数组是一个长度固定的数据类型，数组的长......
  • 【华为OD】D卷真题100分：分割数组的最大差值 Java代码实现[思路+代码]
    【华为OD】2024年C、D卷真题集：最新的真题集题库C/C++/Java/python/JavaScript【华为OD】2024年C、D卷真题集：最新的真题集题库C/C++/Java/python/JavaScript-CSDN博客JS、Java、python、C、C++代码实现：【华为OD】D卷真题100分：分割数组的最大差值JavaScript代码实现[思路+......
  • 一对一直播软件源码，比较常用的数组排序方式有哪些？
    一对一直播软件源码，比较常用的数组排序方式有哪些？一、简单的sort排序：vararr=[1,5,3,87,23];arr.sort(function(a,b){returna-b;})console.log(arr);//输出：[1,23,3,5,87] 注：若返回b-a可获得从大到小的排序；数组的sort方法只能实现简单的按位排序，并不精......
  • java通过冒泡排序对数组进行排序
    冒泡排序是从列表第一个元素开始，比较相邻两个元素大小，小的排在前面，大的排后面，循环反复，小的数据会像气泡那样上浮。packageproject;publicclassMaopaopaixu{ publicstaticvoidmain(String[]args){ //冒泡排序 int[]arr={9,8,3,5,2}; for(inti=0;i<arr.le......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99