[diary of supplementary questions] [2022 Niuke summer school 1] c-grab the seat

Pro

https://ac.nowcoder.com/acm/contest/33186/C

Sol

Through the explanatory diagram of the sample, we can find , The question is actually the number of points on the left of a broken line . According to the range of a point that can be seen, it can be known by the boundary of the screen , Figure to the right of this polyline It is the union of the area surrounded by each point in the graph and the connecting line between the upper and lower points on the screen .

Consider how to maintain this broken line , For each point, the slope of two lines can be maintained ： The line between the point and the upper boundary of the screen ; The line between the point and the lower boundary of the screen . Next, consider why you can calculate the area in this way .

Take the line between the point and the lower boundary of the screen as an example , We enumerate the ordinates from small to large , For each ordinate, if you can find the abscissa of the point on the far right of the polyline , You can subtract to get the number of points that are not blocked , Summation is the answer .

We know , When the ordinate grows from small to large , A line with a small slope may be covered by a line with a large slope , So we save the maximum value of the slope when enumerating , As the slope of the line most likely to block to this point .

Because we maintain the slope , And because the enumeration is the ordinate , So we can directly find the coordinates of the intersection , Because the coordinates of the intersection point may be an integer , So here we have to consider whether we can get the intersection . It's easy to think , If the point is on the line of sight , You can't get , Therefore, the abscissa of the intersection should be subtracted $eps$！！！

In this way, the abscissa value of the intersection can be maintained for each ordinate of the enumeration , The same is true for the other slope of maintenance , Because union set , So take the minimum value in the two cases . The sum of the abscissa of the final intersection is the answer .

Code

//By cls1277
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define endl '\n'

//const LL maxn = ;

int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef DEBUG
    freopen("data.txt","r",stdin);
    #endif
    LL n, m, k, q; cin>>n>>m>>k>>q;
    vector<set<LL>> a(m+1);
    vector<pair<LL, LL>> b(k+1);
    Fo(i,1,k) {
    
        LL x, y; cin>>x>>y;
        b[i] = {
    x, y};
        a[y].insert(x);
    }
    while(q--) {
    
        vector<LL> ans(m+1, 0);
        LL id, x, y; cin>>id>>x>>y;
        a[b[id].second].erase(b[id].first);
        b[id] = {
    x, y};
        a[y].insert(x);
        Fo(i,1,m) {
    
            if(!a[i].size()) ans[i] = n;
            else ans[i] = (*a[i].begin())-1;
        }
        double mx = 0;
        Fo(i,2,m) {
    
            if(mx) ans[i] = (int)min((double)ans[i], (i-1)*1.0/mx-(1e-6));
            if(!a[i].size()) continue;
            double k = (i-1)*1.0/(*a[i].begin());
            mx = max(mx, k);
        }
        mx = 0;
        Ro(i,m-1,1) {
    
            if(mx) ans[i] = (int)min((double)ans[i], (i-m)*1.0/mx-(1e-6));
            if(!a[i].size()) continue;
            double k = (i-m)*1.0/(*a[i].begin());
            mx = min(mx, k);
        }
        LL res = 0;
        Fo(i,1,m) res+=ans[i];
        cout<<res<<endl;
    }
    return 0;
}