A. 楼兰图腾

题意：西部314在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了n个点，经测量发现这n个点的水平位置和竖直位置是两两不同的。西部314认为这幅壁画所包含的信息与这n个点的相对位置有关，因此不妨设坐标分别为(1,y1),(2,y2),…,(n,yn)，其中y1～yn是1到n的一个排列。西部314打算研究这幅壁画中包含着多少个图腾。如果三个点(i,yi),(j,yj),(k,yk)满足1≤i<j<k≤n且yi>yj,yj<yk，则称这三个点构成 V 图腾;如果三个点(i,yi),(j,yj),(k,yk)满足1≤i<j<k≤n且 yi<yj,yj>yk，则称这三个点构成 ∧图腾;西部314想知道，这n个点中两个部落图腾的数目。

题解：

#include <bits/stdc++.h>
using namespace std;

const long long N=2e5+5 ;
long long n,b[N],a[N],s[N],res1,res2;
long long tr[N];

long long lowbit(long long x)
{
	return x & -x;
}

void add(long long x, long long c)
{
	for(long long i = x; i <= n; i += lowbit(i))
		tr[i] += c;
}

long long ask(long long x)
{
	long long res = 0;
	for(long long i = x; i; i -= lowbit(i))
		res += tr[i];
	return res;
}

int main(){
//	ios_base::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>a[i];
	}
	for(long long i=1;i<=n;i++){
		long long y=a[i];
		s[i]=ask(y-1);
		b[i]=i-1-ask(y);
		add(y,1);
	}
	memset(tr,0,sizeof tr);
	for(long long i=n;i>=1;i--){
		long long y=a[i];
		res1+=b[i]*(n-i-ask(y));
		res2+=s[i]*ask(y-1);
		add(y,1);
	}
	cout<<res1<<' '<<res2;
	return 0;
}

B. 一个简单的整数问题

题意：

给定长度为N的数列A，然后输入M行操作指令。第一类指令形如 C l r d，表示把数列中第l～r个数都加d。第二类指令形如 Q x，表示询问数列中第x个数的值。对于每个询问，输出一个整数表示答案。

题解：

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int tr[N],n,m,a[N];
string s;

int lowbit(int x){
	return x & -x;
}

void add(int x,int c){
	for(int i=x;i<=n;i+=lowbit(i))
		tr[i]+=c;
}

int ask(int x){
	int res=0;
	for(int i=x;i;i-=lowbit(i))
		res+=tr[i];
	return res;
}

int main(){
//	ios_base::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	
	for(int i=1;i<=n;i++){
		cin>>a[i];
		add(i,a[i]-a[i-1]);
	}
	for(int i=1;i<=m;i++){
		cin>>s;
		int l,r,d,x;
		if(s=="C"){
			cin>>l>>r>>d;
			add(l,d);add(r+1,-d);
		}
		if(s=="Q"){
			cin>>x;
			cout<<ask(x)<<endl;
		}
	}
	return 0;
}

C. 一个简单的整数问题2

题意：

给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。Q l r，表示询问数列中第 l～r 个数的和。对于每个询问，输出一个整数表示答案。

题解：

#include <bits/stdc++.h>
using namespace std;

const long long N=1e5+5;
long long n,m,a[N],tr1[N],tr2[N],tr[N];
string s;

long long lowbit(long long x){
	return x & -x;
}

void add(long long tr[],long long x,long long c){
	for(long long i=x;i<=n;i+=lowbit(i))
		tr[i]+=c;
}

long long ask(long long tr[],long long x){
	long long res=0;
	for(long long i=x;i;i-=lowbit(i))
		res+=tr[i];
	return res;
}

long long sum(long long x){
	return ask(tr1,x)*(x+1)-ask(tr2,x);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(long long i=1;i<=n;i++){
		cin>>a[i];
	}
	for(long long i=1;i<=n;i++){
		long long b=a[i]-a[i-1];
		add(tr1,i,b);
		add(tr2,i,b*i);
	}
	for(long long i=1;i<=m;i++){
		long long l,r,d;
		cin>>s>>l>>r;
		if(s=="C"){
			cin>>d;
			add(tr1,l,d),add(tr1,r+1,-d);
			add(tr2,l,l*d);
			add(tr2,r+1,(r+1)*-d);
		}else if(s=="Q"){
			cout<<sum(r)-sum(l-1)<<endl;
		}
	}
	return 0;
}