Codeforces Round #510 (Div. 2) D. Petya and Array (codeforces 1042 D)

题目：Petya and Array

题意：
给出一个序列a，求区间[i,j]的个数，使得$\sum_{k=i}^{j} a[k]$∑k=ij​a[k]的值小于t。

思路：
今天考试的一道题——

在完成了分配任务之后，西部314来到了楼兰古城的西部。
相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(‘V’)，一个部落崇拜铁锹(‘∧’)，他们分别用V和∧的形状来代表各自部落的图腾。
西部314在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了N个点，经测量发现这N个点的水平位置和竖直位置是两两不同的。
西部314认为这幅壁画所包含的信息与这N个点的相对位置有关，因此不妨设坐标分别为(1,y1),(2,y2),…,(n,yn),其中y1~yn是1到n的一个排列。
西部314打算研究这幅壁画中包含着多少个图腾，其中V图腾的定义如***意：图腾的形式只和这三个纵坐标的相对大小排列顺序有关）1<=i<j<k<=n且yi>yj,yj<yk;而崇拜∧的部落的图腾被定义为1<=i<j<k<=n且yi<yj,yj>yk;
西部314想知道，这n个点中两个部落图腾的数目。因此，你需要编写一个程序来求出V的个数和∧的个数。

这题的话很明显就是枚举v和∧中间的轴的位置，在求出左边、右边比轴的纵坐标大（小）的数。这就可以用树状数组维护了。
这道题的代码：

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

#define read(x) scanf("%d",&x);
#define ll long long
#define maxn 200000
#define lowbit(x) x&(-x);

int n;
int a[maxn+5];

int sum1[maxn+5],sum2[maxn+5];
int f[maxn+5],g[maxn+5];

int get_sum1(int x) {
	int s=0;
	while(x>0) {
		s+=sum1[x];
		x-=lowbit(x);
	}
	return s;
}

void add1(int x) {
	while(x<=n) {
		sum1[x]++;
		x+=lowbit(x);
	}
}

int get_sum2(int x) {
	int s=0;
	while(x>0) {
		s+=sum2[x];
		x-=lowbit(x);
	}
	return s;
}

void add2(int x) {
	while(x<=n) {
		sum2[x]++;
		x+=lowbit(x);
	}
}

void readin() {
	read(n);
	for(int i=1; i<=n; i++) read(a[i]);
}

int main() {
	readin();
	for(int i=1; i<=n; i++) {
		f[i]=get_sum1(a[i]);
		add1(a[i]);
	}
	for(int i=n; i>=1; i--) {
		g[i]=get_sum2(a[i]);
		add2(a[i]);
	}
	ll ans1=0,ans2=0;
	for(int i=1;i<=n;i++) {
		ans1+=(((ll)(i-1-f[i]))*(n-i-g[i]));
		ans2+=(((ll)f[i])*g[i]);
	}
	printf("%lld %lld",ans1,ans2);
	return 0;
}

然后再看昨天cf这道题，感觉是有相似处的。
可以把序列A处理成前缀和，所求就是i、j的个数，使得A[j]-A[i-1]<t，即A[j]-t<A[i-1]。
假设A[i]的范围在${10}^{6}$106左右，那么这个问题就也可以用树状数组维护，和上面一题类似，每次将A[i-1]加入树状数组，然后查询A[j]-t。
数据范围是${10}^{9}$109的话，由于n只有$2*{10}^5$2∗105，所以可以类似离散化处理下，对于减t后的值，需要二分查找下。
注意需要加一个虚节点0。

代码：

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

#define read(x) scanf("%d",&x);
#define ll long long
#define readll(x) scanf("%lld",&x);
#define lowbit(x) (x&-x)
#define maxn 200000

int n;
ll t;
ll a[maxn+5];
ll b[maxn+5];
ll sum[maxn+5];

void add(ll x) {
	while(x<=n+1){
		sum[x]++;
		x+=lowbit(x);
	}
}

ll getsum(ll x) {
	ll s=0;
	while(x>0) {
		s+=sum[x];
		x-=lowbit(x);
	}
	return s;
}

int main() {
	read(n);readll(t);
	for(int i=1;i<=n;i++) readll(a[i]);
	for(int i=1;i<=n;i++) {
		a[i]+=a[i-1];
		b[i]=a[i];
	}
	sort(b,b+n+1);	//0²ÎÓëÅÅÐò 
	ll ans=0;
	for(int i=1;i<=n;i++) {
		add(lower_bound(b,b+n+1,a[i-1])-b+1);
		ll s=i-getsum(lower_bound(b,b+n+1,a[i]-t+1)-b);
		ans+=s;
	}
	printf("%I64d",ans);
	
	return 0;
}