[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判重

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<map>

 using namespace std;

 map<pair<int,int>,bool> vis;

 int a[],b[];

 int n,p,h,m;

 int main()

 {

     scanf("%d%d%d%d",&n,&p,&h,&m);//本题中给出的p（最高牛的位置）没有用处

     for(int i=,x,y;i<=m;i++)

     {

         scanf("%d%d",&x,&y);

         if(x>y) swap(x,y);// x < y

         if(vis[make_pair(x,y)]) continue;//map判重

         a[x+]--,a[y]++;//差分 影响从a[x+1]开始 持续到a[y-1]

         vis[make_pair(x,y)]=true;

     }

     for(int i=;i<=n;i++)

     {

         b[i]=b[i-]+a[i];

         printf("%d\n",h+b[i]);

     }

     return ;

 }

巴特西

[USACO07JAN]区间统计Tallest Cow

前缀和

差分

最新文章

热门文章