[USACO07JAN]区间统计Tallest Cow

前缀和

sum[i]表示前i个数的和
每次读入a[i]的时候
sum[i] = sum[i - 1] + a[i];

查询l ~ r区间的和： sum[r] - sum[l - 1]

差分

即前缀和的修改操作
我们定义pre[i]表示前i个数需要改变的值
则对一个区间l ~ r + k的操作是
pre[r] + k; pre[l - 1] - k;
则多算的1 ~ l - 1部分就抵消，等价与l ~ r + k;

本题中同一关系可能给出多次，需用map或hash判重

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<map>
 5 using namespace std;
 6 map<pair<int,int>,bool> vis;
 7 int a[10010],b[10010];
 8 int n,p,h,m;
 9 int main()
10 {
11     scanf("%d%d%d%d",&n,&p,&h,&m);//本题中给出的p（最高牛的位置）没有用处 
12     for(int i=1,x,y;i<=m;i++)
13     {
14         scanf("%d%d",&x,&y);
15         if(x>y) swap(x,y);// x < y 
16         if(vis[make_pair(x,y)]) continue;//map判重 
17         a[x+1]--,a[y]++;//差分 影响从a[x+1]开始 持续到a[y-1] 
18         vis[make_pair(x,y)]=true;
19     }
20     for(int i=1;i<=n;i++)
21     {
22         b[i]=b[i-1]+a[i];
23         printf("%d\n",h+b[i]);
24     }
25     return 0;
26 }