线段树应用程序

相关文章http://blog.csdn.net/lisy14/article/details/70141301

#include
#include
using namespace std;
struct node
{
	int down;
	int up;
	node* left;
	node* right;
	int count;
	int nopass;
};

//构建出线段树
node* creat（int downint up）
{
	node* root=new node（）;
	root->up=up;root->down=down;
	if（up-down==0） return root;
	root->left=creat（down（up+down）/2）;
	root->right=creat（（up+down）/2+1up）;
	return root;
}

int Hui（node* rootint iint j）
{
	//递归结束：1.ij没有元素在[downup]里2.root==NULL3.[downup]被i，j完全覆盖
	if（root==NULL） return 0;
	if（（jdown）||（i>root->up）） return root->count;
	if（（i<=root->down）&&（j>=root->up））//[downup]被i，j完全覆盖
	{
		root->count=root->up-root->down+1-root->count;root->nopass=（!root->nopass）;
		return root->count;
	}
	else//否则，对孩子进行递归
	{
		root->count=（Hui（root->leftij）+Hui（root->rightij））;
		return root->count;
	}
}
int Qsn（node*rootint iint j）
{
	//递归结束：1.ij没有元素在[downup]里2.root==NULL3.[downup]被i，j完全覆盖
	if（root==NULL） return 0;
	if（（jdown）||（i>root->up）） return 0;
	if（（i<=root->down）&&（j>=root->up））//[downup]被i，j完全覆盖
	{
		return root->count;
	}
	else//否则，对孩子进行递归
	{
		if（root->nopass==1）
		{
			root->left->count= root->left->up-root->left->down+1-root->left->count;
			root->left->nopass=（!root->left->nopass）;
			root->right->count= root->right->up-root->right->down+1-root->right->count;
			root->right->nopass=（!root->right->nopass）;
			root->nopass=0;
		}
		return （Qsn（root->leftij）+Qsn（root->rightij））; 
	}
}
int main（）
{
	int nm;//n表示扑克牌的数量，m表示操作的函数
	scanf（“%d%d“&n&m）;
	node* root=creat（1n）;
	char op;int ij;
	for（int k=0;k	{
		scanf（“%c“&op）;
		if（op==‘H‘） 
		{
			scanf（“%d%d“&i&j）;
			Hui（rootij）;
		}
		else if（op==‘Q‘） 
		{
			scanf（“%d%d“&i&j）;
			printf（“%d\n“j-i+1-Qsn（rootij））;
		}
		else k--;
	}
	return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2015-12-09 23:47  3_2\
     目录           0  2015-12-08 12:00  3_2\3_2\
     文件        1931  2015-12-09 23:46  3_2\3_2\3_2.cpp
     文件        4004  2015-11-27 23:02  3_2\3_2\3_2.vcxproj
     文件         823  2015-11-27 19:20  3_2\3_2\3_2.vcxproj.filters
     目录           0  2015-12-09 23:41  3_2\3_2\Debug\
     文件          75  2015-12-09 23:41  3_2\3_2\Debug\3_2.lastbuildstate
     文件        2622  2015-12-09 23:41  3_2\3_2\Debug\3_2.log
     文件      134832  2015-12-09 23:41  3_2\3_2\Debug\3_2.obj
     文件        5772  2015-12-09 23:41  3_2\3_2\Debug\CL.read.1.tlog
     文件         254  2015-12-09 23:41  3_2\3_2\Debug\CL.write.1.tlog
     文件         554  2015-12-09 23:41  3_2\3_2\Debug\cl.command.1.tlog
     文件           2  2015-12-09 23:41  3_2\3_2\Debug\link-cvtres.read.1.tlog
     文件           2  2015-12-09 23:41  3_2\3_2\Debug\link-cvtres.write.1.tlog
     文件           2  2015-12-09 23:41  3_2\3_2\Debug\link-rc.read.1.tlog
     文件           2  2015-12-09 23:41  3_2\3_2\Debug\link-rc.write.1.tlog
     文件        1014  2015-12-09 23:41  3_2\3_2\Debug\link.command.1.tlog
     文件        2190  2015-12-09 23:41  3_2\3_2\Debug\link.read.1.tlog
     文件         324  2015-12-09 23:41  3_2\3_2\Debug\link.write.1.tlog
     文件      240640  2015-12-09 23:41  3_2\3_2\Debug\vc110.idb
     文件      331776  2015-12-09 23:41  3_2\3_2\Debug\vc110.pdb
     文件     7143424  2015-12-09 23:47  3_2\3_2.sdf
     文件         876  2015-11-27 19:20  3_2\3_2.sln
     文件       25088  2015-12-09 23:47  3_2\3_2.v11.suo
     目录           0  2015-12-08 12:00  3_2\Debug\
     文件       62976  2015-12-09 23:41  3_2\Debug\3_2.exe
     文件      765268  2015-12-09 23:41  3_2\Debug\3_2.ilk
     文件      789504  2015-12-09 23:41  3_2\Debug\3_2.pdb
     文件       20133  2015-12-12 11:19  3_2.docx