洛谷P 2184貪欲大陸題解

洛谷P 2184貪欲大陸題解

題

タイトル説明

入出力フォーマット:

入力フォーマット

出力フォーマット

入出力サンプル

入力サンプル

出力サンプル

データ範囲

解析

コード

タイトルリンク
タイトル
タイトルの説明
アリたちの狂気の攻撃に、FFのTower defenceは失敗を宣言する……人間はアリたちにGreed Islandの上の湾に追い込まれる.今、FFちゃんの後方は見渡す限りの海で、前方は変異したスーパーアリです.FFさんはまだいい前途があるので、命を落とすつもりはありません.そこで、部下を派遣してSCVを改造して地雷を配置し、アリたちの攻撃を阻止しました.小FFの最後の防御線は長さNの塹壕で、小FFは無数の地雷を持っているが、SCVは毎回[L,R][L,R][L,R]区間に同じ以前に埋められた地雷を埋めることができる.状況はすでに十万火急なので、FFさんは時々「L',R'」[L',R'][L',R']区間に何種類の異なる地雷があるかを尋ねるかもしれませんが、できるだけ早く返事をしてほしいと思っています.
入出力フォーマット:
入力フォーマット
第1の挙動の2つの整数n n n nおよびmmmn n n nは防御線長を表し,mmはSCVブレイ回数および小FF問合せ回数の合計を表す.次にm行があり、各行の3つの整数Q、L、R Q、L、R Q、L、R;Q=1 Q=1 Q=1はSCVが[L,R]区間に1種の地雷を敷くことを示し,Q=2 Q=2は小FFが現在の[L,R]区間に合計何種の地雷があるかを尋ねることを示す.
出力フォーマット
FFの各質問に対して,現在の区間地雷総数を示す答え(単独行)を出力する.
入出力サンプル
入力サンプル

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

出力サンプル

1
2

データ範囲
30%のデータ:0≦n,m≦1000 0le n,mle 1000 0≦n,m≦1000;100%のデータ:0≦n,m≦1 0 5 0le n,mle 10^5 0≦n,m≦105.
解析
L L LからR R R Rの間にどれだけの種類の地雷があることを求めて、地雷を放すのはすべて区間によって放すので、その上毎回放す地雷はすべて異なって、では1 1 1からL L Lの地雷種数(つまり1から1 L Lの地雷放置開始個数)から1 1からR−1 R−1 R−1 R−1 R−1が放置済みの地雷(つまり地雷放置時のR R R R)種数を減算すれば解答となる.次は簡単ですが、2つのツリー配列で2つの接頭辞和を維持すればいいです.
コード#コード#

#include
using namespace std;
int n,m;
int q,l,r;
const int Maxn=100010;
int Ar1[Maxn],Ar2[Maxn];
int lowbit(int x)
{
     
	return x&(-x);
}
void update1(int x)
{
     
	while(x<=n)
	{
     
		Ar1[x]++;
		x+=lowbit(x);
	}
}
void update2(int x)
{
     
	while(x<=n)
	{
     
		Ar2[x]++;
		x+=lowbit(x);
	}
}
int ask1(int x)
{
     
	int ans=0;
	while(x)
	{
     
		ans+=Ar1[x];
		x-=lowbit(x);
	}
	return ans;
}
int ask2(int x)
{
     
	int ans=0;
	while(x)
	{
     
		ans+=Ar2[x];
		x-=lowbit(x);
	}
	return ans;
}
int main()
{
     
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
     
		scanf("%d%d%d",&q,&l,&r);
		if(q==1)
		{
     
			update1(l);
			update2(r);
		}else{
     
			printf("%d
",ask1(r)-ask2(l-1));
		}
	}
	return 0;
}

はい、今日の話は終わりました.何か質問があったら私に聞いてください.私のブログに質問があったら、私に修正を注意してください.