排序 – GNAQ 的心语屋

Time Limit: 40 Sec (Total)

Memory Limit: 128 MB

莫队+树状数组维护

类(jiu)似(shi)冒泡排序的过程

注意优化时间

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;cstdlib&gt;
#include&lt;algorithm&gt;
#include&lt;iterator&gt;
using namespace std;

int n,m,seq[100010]={0},fwt[100010]={0},setx[100010]={0},blksz=0,setlen=0;
struct asksx
{
	int codex,lx,rx,ans;
}ask[100010]={0};
int nowans=0;

inline void readx(int&amp; x)
{
	x=0; int k=1; register char ch=0;
	while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline int BinSearch(int val)
{
	int l=1,r=setlen,mid;
	while (1)
	{
		mid=(l+r)&gt;&gt;1;
		if (setx[mid]==val) return mid;
		else if (setx[mid]&gt;val) r=mid-1;
		else l=mid+1;
	}
}

inline void process1()
{
	setlen=n;
	memcpy(setx,seq,sizeof(seq));
	sort(setx+1,setx+n+1);
	for (int i=1;i&lt;=n;i++) if (setx[i]==setx[i+1]) { setx[i]=2*1e9; setlen--; }
	sort(setx+1,setx+n+1);
	for (int i=1;i&lt;=n;i++) seq[i]=BinSearch(seq[i]);
}

inline bool cmp1(asksx a,asksx b)
{
	if ((a.lx/blksz)==(b.lx/blksz)) return a.rx&lt;b.rx;
	else return a.lx&lt;b.lx;
}
inline bool cmp2(asksx a,asksx b) { return a.codex&lt;b.codex; }

inline void update(int pos,int val)
{
	while (pos&lt;=setlen)
	{
		fwt[pos]+=val;
		pos+=(pos&amp;(-pos));
	}
}

inline int query(int pos)
{
	int sum=0;
	while (pos)
	{
		sum+=fwt[pos];
		pos-=(pos&amp;(-pos));
	}
	return sum;
}

int main()
{
	readx(n); blksz=sqrt(n);
	for (int i=1;i&lt;=n;i++) readx(seq[i]);
	readx(m);
	for (int i=1;i&lt;=m;i++)
	{
		ask[i].codex=i;
		readx(ask[i].lx); readx(ask[i].rx);
	}
	process1();
	sort(ask+1,ask+m+1,cmp1); int lpos=1,rpos=0;
	for (int i=1;i&lt;=m;i++)
	{
		while (rpos&lt;ask[i].rx)
		{
			rpos++;
			update(seq[rpos],1); nowans+=(query(setlen)-query(seq[rpos]));
		}
		while (rpos&gt;ask[i].rx)
		{
			update(seq[rpos],-1); nowans-=(query(setlen)-query(seq[rpos]));
			rpos--;
		}
		while (lpos&lt;ask[i].lx)
		{
			update(seq[lpos],-1); nowans-=query(seq[lpos]-1);
			lpos++;
		}
		while (lpos&gt;ask[i].lx)
		{
			lpos--;
			update(seq[lpos],1); nowans+=query(seq[lpos]-1);
		}
		
		ask[i].ans=nowans;
	}
	
	sort(ask+1,ask+m+1,cmp2);
	for (int i=1;i&lt;=m;i++) printf("%d\n",ask[i].ans);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<cstdlib>

#include<algorithm>

#include<iterator>

using namespace std;

int n,m,seq[100010]={0},fwt[100010]={0},setx[100010]={0},blksz=0,setlen=0;

struct asksx

{

int codex,lx,rx,ans;

}ask[100010]={0};

int nowans=0;

inline void readx(int& x)

{

x=0; int k=1; register char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

inline int BinSearch(int val)

{

int l=1,r=setlen,mid;

while (1)

{

mid=(l+r)>>1;

if (setx[mid]==val) return mid;

else if (setx[mid]>val) r=mid-1;

else l=mid+1;

}

inline void process1()

{

setlen=n;

memcpy(setx,seq,sizeof(seq));

sort(setx+1,setx+n+1);

for (int i=1;i<=n;i++) if (setx[i]==setx[i+1]) { setx[i]=2*1e9; setlen--; }

sort(setx+1,setx+n+1);

for (int i=1;i<=n;i++) seq[i]=BinSearch(seq[i]);

}

inline bool cmp1(asksx a,asksx b)

{

if ((a.lx/blksz)==(b.lx/blksz)) return a.rx<b.rx;

else return a.lx<b.lx;

}

inline bool cmp2(asksx a,asksx b) { return a.codex<b.codex; }

inline void update(int pos,int val)

{

while (pos<=setlen)

{

fwt[pos]+=val;

pos+=(pos&(-pos));

}

inline int query(int pos)

{

int sum=0;

while (pos)

{

sum+=fwt[pos];

pos-=(pos&(-pos));

}

return sum;

}

int main()

{

readx(n); blksz=sqrt(n);

for (int i=1;i<=n;i++) readx(seq[i]);

readx(m);

for (int i=1;i<=m;i++)

{

ask[i].codex=i;

readx(ask[i].lx); readx(ask[i].rx);

}

process1();

sort(ask+1,ask+m+1,cmp1); int lpos=1,rpos=0;

for (int i=1;i<=m;i++)

{

while (rpos<ask[i].rx)

{

rpos++;

update(seq[rpos],1); nowans+=(query(setlen)-query(seq[rpos]));

}

while (rpos>ask[i].rx)

{

update(seq[rpos],-1); nowans-=(query(setlen)-query(seq[rpos]));

rpos--;

}

while (lpos<ask[i].lx)

{

update(seq[lpos],-1); nowans-=query(seq[lpos]-1);

lpos++;

}

while (lpos>ask[i].lx)

{

lpos--;

update(seq[lpos],1); nowans+=query(seq[lpos]-1);

}

ask[i].ans=nowans;

}

sort(ask+1,ask+m+1,cmp2);

for (int i=1;i<=m;i++) printf("%d\n",ask[i].ans);

return 0;

}

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

输入输出格式

输入格式：

第一行：一个整数N，表示项链的长度。

第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。

第三行：一个整数M，表示HH 询问的个数。

接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。

输出格式：

M 行，每行一个整数，依次表示询问对应的答案

什么描述啊……

我们可以 ~~简单地~~ 发现对于每次区间询问，如果一种编号出现了多次，那么只有最后一次才是有意义的。

那么离线询问并按照R为第一关键字，L为第二关键字排序。

然后从当前位置指针（初始为1，当然）扫到R统计有没有新出现的和重复出现的

如果是新出现的那么标记一下再扔到树状数组里（哦，忘记了，树状数组是按位置建的，也就是下标和项链是对应的）

如果是重复出现的，那么，有一个数组保存之前出现的位置，get到这个位置然后往树状数组里这个位置扔一个-1就行了。

之后更新前一次出现位置数组并扔进树状数组里。

最后求区间和……

真是一道好题。

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;algorithm&gt;
#include&lt;iterator&gt;
#include&lt;utility&gt;
using namespace std;

//data
struct qu
{
	int left,right,code;
}query[50010]={0};
int len,nec[50010]={0},qnum;
//tree
int fwt[50010]={0};
bool have[1000010]={0};
int firstplace[1000010]={0};
//count ans
int ans[100010]={0};

bool cmp(qu a,qu b)
{
	if (a.right==b.right) return a.left&lt;b.left;
	return a.right&lt;b.right;
}

void add(int pos,int val)
{
	while (pos&lt;=len)
	{
		fwt[pos]+=val;
		pos+=pos&amp;(-pos);
	}
}

int getsum(int pos)
{
	int res=0;
	while (pos)
	{
		res+=fwt[pos];
		pos-=pos&amp;(-pos);
	}
	return res;
}

int main()
{
	scanf("%d",&amp;len);
	for (int i=1;i&lt;=len;i++) scanf("%d",&amp;nec[i]);
	scanf("%d",&amp;qnum);
	for (int i=1;i&lt;=qnum;i++) 
	{
		scanf("%d%d",&amp;query[i].left,&amp;query[i].right);
		query[i].code=i;
	}
	sort(query+1,query+qnum+1,cmp);
	
	int totp=0;
	for (int i=1;i&lt;=qnum;i++)
	{
		while (totp&lt;query[i].right)
		{
			totp++;
			if (!have[nec[totp]]) have[nec[totp]]=true;
			else add(firstplace[nec[totp]],-1);
			
			firstplace[nec[totp]]=totp;
			add(totp,1);
		}
		
		ans[query[i].code]=getsum(query[i].right)-getsum(query[i].left-1);
	}
	
	for (int i=1;i&lt;=qnum;i++)  printf("%d\n",ans[i]);
	return 0;
}

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<iterator>

#include<utility>

using namespace std;

//data

struct qu

{

int left,right,code;

}query[50010]={0};

int len,nec[50010]={0},qnum;

//tree

int fwt[50010]={0};

bool have[1000010]={0};

int firstplace[1000010]={0};

//count ans

int ans[100010]={0};

bool cmp(qu a,qu b)

{

if (a.right==b.right) return a.left<b.left;

return a.right<b.right;

}

void add(int pos,int val)

{

while (pos<=len)

{

fwt[pos]+=val;

pos+=pos&(-pos);

}

int getsum(int pos)

{

int res=0;

while (pos)

{

res+=fwt[pos];

pos-=pos&(-pos);

}

return res;

}

int main()

{

scanf("%d",&len);

for (int i=1;i<=len;i++) scanf("%d",&nec[i]);

scanf("%d",&qnum);

for (int i=1;i<=qnum;i++)

{

scanf("%d%d",&query[i].left,&query[i].right);

query[i].code=i;

}

sort(query+1,query+qnum+1,cmp);

int totp=0;

for (int i=1;i<=qnum;i++)

{

while (totp<query[i].right)

{

totp++;

if (!have[nec[totp]]) have[nec[totp]]=true;

else add(firstplace[nec[totp]],-1);

firstplace[nec[totp]]=totp;

add(totp,1);

}

ans[query[i].code]=getsum(query[i].right)-getsum(query[i].left-1);

}

for (int i=1;i<=qnum;i++) printf("%d\n",ans[i]);

return 0;

}

分类：排序

BZOJ3289 Mato的文件管理

BZOJ1878 | SDOI2009 HH的项链

题目描述

输入输出格式