C. Grab the Seat!

题解

观察数据范围发现$qq$很小，$O(n)O(n)$的复杂度可以通过，考虑对每次询问分别独立地去求解。

观察出一个重要性质：一个被占的座位与屏幕两端连线所夹的区域以外都是会被挡住的点（动手画一画就能看出来）。

实际上，一个被占的座位所去掉的点可以被分成三个部分：只被与(0,1)连线所决定的部分、只被与(0,m)连线所决定的部分、同时被两条连线决定的部分，这就相当于将与(0,1)连线确定的部分和与(0,m)连线确定的部分求并。

那么如何维护一条线决定的部分呢，不难发现对于y相同的座位，最终没有被去掉的座位一定是从(1,y)开始的一段连续区间，而所有连线都过同一点，因此其覆盖的范围只与斜率有关，所以我们考虑维护此时斜率的最大或最小值，逐行考虑，就可以求出每一行的可选座位数量，对于两种连线求min就得到最终一行可选座位的数量。

复杂度$O((n+m)q)O((n+m)q)$

int minn[N], x[N], y[N], res[2][N];

int main() {
    int m = fast_IO::read(), n = fast_IO::read(), k = fast_IO::read(), q = fast_IO::read();
    for (int i = 1; i <= k; ++i)
        x[i] = fast_IO::read(), y[i] = fast_IO::read();
    while (q--) {
        int p = fast_IO::read();
        x[p] = fast_IO::read(), y[p] = fast_IO::read();
        for (int i = 1; i <= n; ++i)
            minn[i] = m + 1;
        for (int i = 1; i <= k; ++i)
            minn[y[i]] = min(minn[y[i]], x[i]);
        res[0][1] = minn[1] - 1;
        int now = 1;
        for (int i = 2; i <= n; ++i) {
            if ((ll)(i - 1) * minn[now] > (ll)(now - 1) * minn[i])
                now = i;
            //y=(now-1)/minn[now]*x+1
            //x=(y-1)*minn[now]/(now-1)
            res[0][i] = ((ll)(i - 1) * minn[now] - 1) / (now - 1);
        }
        res[1][n] = minn[n] - 1;
        now = n;
        for (int i = n - 1; i; --i) {
            if ((ll)(n - i) * minn[now] > (ll)(n - now) * minn[i])
                now = i;
            //y=(now-n)/minn[now]*x+n
            //x=(y-n)*minn[now]/(now-n)
            res[1][i] = ((ll)(n - i) * minn[now] - 1) / (n - now);
        }
        ll ans = 0;
        for (int i = 1; i <= n; ++i)
            ans += min(res[0][i], res[1][i]);
        printf("%lld\n", ans);
    }
    return 0;
}