题目：Petya and Array
题意：
给出一个序列a，求区间[i,j]的个数，使得 ∑ k = i j a [ k ] \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 {10}^{6} 106左右，那么这个问题就也可以用树状数组维护，和上面一题类似，每次将A[i-1]加入树状数组，然后查询A[j]-t。
数据范围是 10 9 {10}^{9} 109的话，由于n只有 2 ? 10 5 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 200000int 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; }