天天看點
傳回

資料結構

資料結構

隊列和棧 

queue<int>q;
int n;

int main() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
  n=read();
  for (int i=1;i<=n;i++) 
  {
    int opt=read();
    if(opt==1){
      int x=read();
      q.push(x);
    }
    else {
      printf("%d\n",q.front());
      q.pop();
    }
  } 
  fclose(stdin);
  fclose(stdout);
  return 0;
}


           
int st[B], head=0, tail=0, n;

int main() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
  n=read();
  for (int i=1;i<=n;i++)
  {
    int opt=read();
    if(opt==1)
    {
      int x=read();
      st[++head]=x;
    }
    else{
      printf("%d\n", st[head]);
      head--;
    }
  }
  fclose(stdin);
  fclose(stdout);
  return 0;
}

單調隊列（松弛操作） 

/*暴力O（n^2)*/
for (int a=1;a<=n-k+1;i++)
{
	int ans=oo;
	for (int b=0;b<k;b++)
	{
		ans=min(ans,z[a+b]);
	}
	printf("%d\n",ans);
}

法1 單調隊列

本質：在前面删一個數，從後面加一個數。隊列+最小值

樣例

1 3 -1 -3 5 3 6 7， 3

要求最小值，維護單調遞增的，

不單調的本質就是最後的數和他不是遞增的，是以扔掉就好了，

保持單調遞增根最小值有啥關系呢？

單調隊列中隊首就是我們需要的最小值，維護區間長度就是判斷隊尾和隊首是否存在來維護即可

int z[B], n;

struct monotone_queue//單調遞增
{
	int head,tail;
	int q[233333];
	monotone_queue()
	{
	head=1,tail=0;
	}
	void push(int p)
	{
		while (head<=tail && z[q[tail]] >= z[p]) tail--;
		q[++tail]=p;
	}
	int front (){
	 return q[head];
	}
	void pop()
	{
		head++;
	}
}q;

int main()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++)
	scanf("%d",&z[i]);
	for (int i=1;i<=k;i++)
		q.push(i);//放入隊列的是坐标
	printf("%d\n", z[q.front()]);
	for (int a=k+1;a<=n;a++)
	{
		q.push(a);
		if (q.front()==a-k) q.pop();
		printf("%d\n", z[q.front()]);
	}
}

法2 ST表

\(O(nlogn)\)

例題

筆記

思路

如果 \(l=1\) 那麼怎麼找右 \(r\);

int n, k;
int z[23333];

int l=1,r=1;
int sum=z[1];

while(sum<k)
{
	r++;
	sum+==z[r];
}
ans=min(ans, l-r+1)// 左端點為1時，滿足條件區間時多少

那麼 \(l=2\) 時呢，同理

那麼請問，\(r1,r2\) 之間有什麼關系 \(r2>r1\),這裡指的是坐标

int n, k;
int z[23333];

int l=1,r=1;
int sum=z[1];

for (int l=1,r=1,sum=z[l];r>=n;)
{
    while(r<n && sum<k)
    {
        r++;
        sum+=z[r];
    }
    if(sum>=k) ans=min(ans, r-l+1);
    else break;
    sum-=z[l];
    l++;
}

複雜度是 \(O(n)\) 每個元素隻會被加入一次和出隊一次，而且隊首和隊尾循環時獨立的并不沖突，是以總的複雜度為 \(O(n)\),

共同性：當區間左端點右移的時候，右端點也一定右移，

ＳＴＬ

雙端對列 \(deque\)

include <deque>

void push(int p)
{
	while (q.size() && z[q.back()] >= z[p])
		q.pop_back();
	q.push_back();
}

int main()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++)
	scanf("%d",&z[i]);
	for (int i=1;i<=k;i++)
		q.push(i);//放入隊列的是坐标
	printf("%d\n", z[q.front()]);
	for (int a=k+1;a<=n;a++)
	{
		q.push(a);
		if (q.front()==a-k) q.pop_front();
		printf("%d\n", z[q.front()]);
	}
}

堆

大根堆

  • 加入一個數
  • 詢問最大值
  • 删除最大值

小根堆

  • 相反即可

STL

大根堆-

priority_queue<int> head

小根堆-将數字取個負數（相反數）

手寫堆

一 如何構造二叉樹

二 如何完成堆

大根堆：任何一個點的值都不小于兒子的值

隻能删掉最大值！

srtuct heap{
	int n;//元素個數
	int z[2333333];//村原屬；
	heap()
	{
		n=0;
	}
	
	int size()
	{
		return n;
	}
	int push()//加入x
	{
		n++;
		z[n]=x;
		int p=n;
		while (p!=1)
		{
			int f=p/2;
			if (z[f]<z[p])//父親節點是p/2
			{
				swap(z[f],z[p]);
	               p=f;//一直換
			}
			else break;
		}
	}
	int pop()//删除最大值
	{
		swap([z[1],z[n]]);
        n--;//保證樹的形态沒改變,但是堆的性質沒了，是以就需要頭不斷的向下換
        
        int p=1;
        while (p*2<=n)
        {
            int pp=p*2;//比較兩個兒子的大小
            if (pp+1 <= n && z[pp+1] > z[pp]) pp+=1;
            if (z[p] < z[pp])
            {
                swap(z[p], z[pp]);
                p=pp;
            }
            else break;
        }
	}
	int top()
	{
		return z[1];
	}
}

樹狀數組

有 \(N\) 個數 \(a_1,a_2...，a_n\),
  • 将 \(a_i\) 加上 \(v\);
  • 詢問 \([l,r]\) 區間和

超級快，常數比較小，解決資料小的，且功能小；

\(lowbit(x)=2^y\) 得到數中最多的 \(2^n\)

\(y_i\) 從 \(i\) 點往下走能走到 \(z\) 位置的和；

\(y_i=z_i+z_{i-1}...+z_{i-lowbit(i)+1}\)

是以詢問 \([l,r]\) 和就是字首和，就是 \([1,r]-[1,l-1]\)

那麼怎麼詢問 \([1,p]\) 和？

\[s(p)=\begin{matrix}y(p)\\\overbrace{a_p+a_{p-1}+a_{p-2}+a_{p-lowbit(p)}}\end{matrix}

+\begin{matrix}y(p-lowbit(p))\\\overbrace{aa_{p-lowbit(p)+1}...+a_1}\end{matrix}

\]

#define lb(x) x&(-x)

int n, y[23333];


void modify(int p, int v)
{
	for (;p<=n;p+=lb(p)) y[p]+=v;
}

int query(int p)
{
	int ans=0;
	for (;p-=lb(p);) ans+=y[p];
	return ans;
}

int main()
{
	scanf("%d",&n);
    //發一預處理
    for (int a=1;a<=n;a+=2)
        	lb[a]=1;
    for (int a=1;a<=n/2;a++)
        	lb[a*2]=lb[a]*2;
	for (int i=1;i<=n;i++)
	{
		int v;
		scanf("%d",&v);
		modify(a,v);
	}
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
	{
		int p, v;
		modify(p,v);
		query(p);
	}
}

單點詢問，區間修改

差分的思想就将單點詢問轉換成區間詢問

有多少對逆序對？

對于一個數 \(a_i\) 他能産生的逆序對就是比前面小的，比後面大的即可，

那麼先考慮隻有前面的

#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define lb(x) x&(-x)
using namespace std;

const int A = 1e5 + 11;
const int B = 1e8 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int read() {
  char c = getchar();
  int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}

int m, y[B], z[B],n;

void updata(int x,int v){
  for (;x<=n;x+=lb(x)) y[x]+=v;
}

int query(int x)
{
  int ans=0;
  for (;x;x-=lb(x)) ans+=y[x];
  return ans;
}
  

int main() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
  m=read();
  for (int i=1;i<=m;i++)
    scanf("%d",&z[i]), n=max(n,z[i]);
  int ans=0;
  for (int i=1;i<=m;i++)
  {
    updata(z[i],1);
    ans+=query(n)-query(z[i]);
  }
  printf("%d\n",ans);
  fclose(stdin);
  fclose(stdout);
  return 0;
}

problem 14

1-N的無序排列，做旋轉置換，問怎樣的置換能夠使得得到的逆序對最小 
int m, y[B], z[B],n;

void updata(int x,int v){
  for (;x<=n;x+=lb(x)) y[x]+=v;
}

int query(int x)
{
  int ans=0;
  for (;x;x-=lb(x)) ans+=y[x];
  return ans;
}
  

int main() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
  n=read();
  int ans=0;
  for (int i=1;i<=n;i++) updata(i,1);
  for (int i=1;i<=n;i++)
  {
    cin>>z[i];
    updata(z[i]+1,-1);
    ans+=query(z[i]+1);
  }
  int sum=ans;
  for (int i=1;i<=n;i++)
  {
    ans+=(-z[i]+n-z[i]-1);
    if (ans<sum)
      sum=ans;
  }
  cout << sum;
}
筆記
上一篇: 整數劃分模型
下一篇: 2/17qbxt筆記

繼續閱讀