一开始的思路是把限制放入队列，然后线段树去维护中间的值。

但是发现队列的进入顺序可能会造成错误，就没想了。

这里有个很重要的条件，就是给出的这头牛是最高的牛。

然后，很显然的一点就是对于给出的限制条件，中间的牛肯定至少要比两端的牛小1。

对于这步思路，我们就将中间所有的牛都 -1，这样就把关系虚地更新着。

最后再去加上H就行，因为H是最高的牛。

中间的更新可以用差分。

这里重复的话会多算，所以要去重。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 10005;
const int M = 2e3 + 5;
const LL Mod = 2147483647;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
    inline LL read(){
        LL x = 0,f = 1;char c = getchar();
        while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
        while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
        return x*f;
    }
}
using namespace FASTIO;

int d[N];
map<pii,int> mp;
int main()
{
    int n,pos,H,m;
    n = read(),pos = read(),H = read(),m = read();
    while(m--) {
        int x,y;x = read(),y = read();
        if(x > y) swap(x,y);
        if(mp[pii(x,y)] == 1) continue;
        d[x + 1]--;
        d[y]++;
        mp[pii(x,y)] = 1;
    }
    int sum = 0;
    for(int i = 1;i <= n;++i) {
        sum += d[i];
        printf("%d\n",H + sum);
    }
    system("pause");
    return 0;
}

View Code

对于线段树的做法，其实也是可行的。

对于一个位置的操作，我们需要等他的所有相关操作都完成这样才不会造成影响，但是相关操作之后又有着次序的限制。

于是就想到了拓扑，我们拓扑建边，这里建边我们从大的边往小的建，因为对于限制条件x,y我们可以知道x <= y。

最后就可以拓扑然后线段树去修改。