程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 2852 （樹狀數組求第 k個 大於a 的數）

HDU 2852 （樹狀數組求第 k個 大於a 的數）

編輯：C++入門知識


題意：


三種操作


0 x： 向容器裡加入x;
1 x: 在容器內刪除x，不存在x則輸出“No Elment”

2 x y: 在容器中找到大於x的第y個數，沒有則輸出“Not Find”


題解： 樹狀數組


操作1： 直接add(x,1)
操作2： 查找sum(x)和sum(x-1)，差值為0則不存在x,反之，add(x,-1)即可刪除一個x
操作3： 首先查找小於等於x的個數s，則找到大於x的第y個數相當於找到第s+y小數 




#include   
#include   
#include   
#include  
#include 
#include   
#include  
#include  
#define M 100005  
#define INF 0x7ffffff 
#define LL __int64
using namespace std;  

int c[M];
int lowBit(int x)
{
	return x&(-x);
}

void update(int pos,int v)
{
	while(posmid)
				ans=mid;
		}
	}
	if(ans==M)
		printf("Not Find!\n");
	else printf("%d\n",ans);
}
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		int p,e,a,k;
		memset(c,0,sizeof(c));
		while(n--)
		{
			scanf("%d",&p);
			if(p==0)
			{
				scanf("%d",&e);
				update(e,1);
			}
			else if(p==1)
			{
				scanf("%d",&e);
				if(getSum(e)-getSum(e-1)==0)
					printf("No Elment!\n");
				else update(e,-1);
			}
			else 
			{
				scanf("%d%d",&a,&k);
				cal(a,k);
			}
		}
	}
	return 0;
}


  1. 上一頁:
  2. 下一頁:
C++入門知識
用數組實現從文件搜索帳戶和驗證密碼，數組帳戶驗證密碼

用數組實現從文件搜索帳戶和驗證密碼，數組帳戶驗證密碼&nbs
Using UIPageControl as a container UIViewController

雖然看上去用 UIPageControl 在一系列 U
為C++標准庫容器寫自己的內存分配程序

　　根據sgi 的STL源碼的二級分配算法改寫的內存
leetcode筆記：Linked List Cycle 2

leetcode筆記：Linked List Cycle 2
[leetcode]Valid Sudoku

[leetcode]Valid Sudoku 問題描述：
矩陣乘法 之 strassen 算法

一般情況下矩陣乘法需要三個for循環，時間復雜度為O(
相關文章
閱讀排行榜
TM1668 Led 驅動芯片源程序 Codeforces 327B-Hungry Sequence(素數篩) 一個線程池的簡單的實現 Petya and Coloring POJ 3254 Corn Fields [狀壓DP] uva 11525排列（樹狀數組 + 二分） _T("") vs L 到底用誰？L！ HDOJ 4964 Emmet 通過文件句柄獲得文件路徑 UVA 11389　The Bus Driver Problem（貪心） 數據結構與算法系列（1）-單鏈表類的實現（C++)
熱門圖文
OWA中添加大附件的實現基礎教程 jquery對象-jQuery對象中，this指向哪個對象 OLTP應用之MySQL架構選型 PHP獲取表單步驟總結 Java常量的應用，Java常量應用 C++智能指針循環引用解決 哈夫曼樹原理及構造（轉載），哈夫曼 C++解析xml利器—tinyxml圖解法
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved