树状数组(离线)

对于一些询问左右区间的题可以把询问离线出来在按右端点排序
用右端点从左往右扩计算当前右端点对所有左端点的贡献累加在左端点
区间加可用差分来做然后用树状数组求答案

eg:

独立

描述

区间中一个数若在该区间中只出现一次，则称其为独立的。

给出一个数列， \(a_1,a_2,⋯,a_n\)

\(m\) 次求区间中所有独立的数的和。

输入
第一行两个正整数 \(n,m\)
第二行 \(n\) 个正整数 \(a_1,a_2,⋯,a_n\)
接下来 \(m\) 行，每行两个正整数 \(l,r\) 表示询问区间 \([l,r]\) 中独立数的和

输出
\(m\) 行，每行一个正整数为对应询问的答案

样例
\(input1\)

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

\(output1\)
8
9
0

\(explanation1\)

\(8=1+4+38=1+4+3\)
\(9=2+3+49=2+3+4\)
区间 \([4,5]\)中没有独立数

范围
\(12\)% \(n≤200,m≤1000\)
\(40\)% \(n≤2000,m≤5000\)
\(100\)% \(n≤2×10^5,m≤5×10^5\)
对于所有数据 \(1≤ai≤n,1≤l≤r≤n\)

限制
\(1s\)

\(128M\)

std

#include<bits/stdc++.h>
using namespace std;
#define lb(x) x&(-x)
const int N = 5e5+9;
typedef long long ll;
int n,m,a[N],pre[N],pos[N];
ll c[N];
struct Q
{
	int l,r,id;
	ll ans;
}q[N];
bool cmp(Q x,Q y){return x.r < y.r;}
bool cmp1(Q x,Q y){return x.id < y.id;}
void modify(int x,int v)
{
	if(x == 0)return;
	for(;x <= n;x+=lb(x))
		c[x] += v;
}

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

int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i++)
	{
		scanf("%d",&a[i]);
		pre[i] = pos[a[i]];	
		pos[a[i]] = i;
	}
	for(int i = 1;i <= m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id = i;
	sort(q+1,q+1+m,cmp);
	
	int p = 1;
	for(int i = 1;i <= m;i++)
	{
		int l = q[i].l,r = q[i].r;
		for(;p <= r;p++)
		{
			if(pre[p])//消除上一个a[i]对左端点的贡献
			{
				modify(pre[pre[p]]+1,-a[p]);
				modify(pre[p]+1,a[p]);
			}
			modify(pre[p]+1,a[p]);
			modify(p+1,-a[p]); 
		}
		q[i].ans = query(l);
	}
	
	sort(q+1,q+1+m,cmp1);
	for(int i= 1;i <= m;i++)printf("%lld\n",q[i].ans);
	return 0;
}

HH的项链做法与这题做法相似但是这题思维难较大一点