题解：AT_arc210_a [ARC210A] Always Increasing

· · 题解

AT_arc210_a [ARC210A] Always Increasing 题解

差分约束是神！

线段树 101 ms

差分约束 33 ms

首先我们发现要维护的是一堆的大于信息。

需要构造初始的数列，我们不妨设初始数列的第 i 项为 x_i。

这样，就相当于初始是一堆未知量。

对于每次操作，设操作的点为 pos，我们发现只会有 x_{pos} 和 x_{pos + 1} 的关系需要更新（因为要保证每次操作结束后 x_{pos} < x_{pos + 1}）。

于是我们把每次操作形成的新的约束条件记录下来，再加上初始的约束条件（初始数列单调上升），直接跑一遍差分约束即可。

跑的飞快啊，至少比我写的线段树快的多的多qwq。

最后，附上代码。

#include <iostream>
#include <stdio.h>
#include <queue>
#define int long long 
#define add(u,v,z) to[++ tot] = v,w[tot] = z,nxt[tot] = h[u],h[u] = tot
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
#define Blue_Archive return 0
using namespace std;
constexpr int N = 2e5 + 3;
constexpr int M = 1e6 + 3;
constexpr int INF = 1e9;

int T;
int n;
int m;
int ans;
int tot;
int h[N];
int w[M];
int to[M];
int nxt[M];
int dis[N];
int cnt[N];
int laz[N];

bool vis[N];

queue<int> q;

inline int read()
{
    int x = 0,f = 1;
    int c = getchar_unlocked();
    while(c < '0' || c > '9') f = (c == '-' ? -1 : f),c = getchar_unlocked();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar_unlocked();
    return x * f;
}

inline void write(int x)
{
    if(x < 0) x = -x,putchar_unlocked('-');
    if(x > 9) write(x / 10);
    putchar_unlocked(x % 10 + '0');
}

inline bool spfa()
{
    for(int i = 1;i <= n + 1;i ++) dis[i] = INF,cnt[i] = 0;
    dis[n + 1] = 0;
    q.push(n + 1);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        if(cnt[u] > n) return 0;
        cnt[u] ++;
        for(int i = h[u];i;i = nxt[i])  
        {
            if(dis[to[i]] > dis[u] + w[i])
            {
                dis[to[i]] = dis[u] + w[i];
                q.push(to[i]);
            }
        }
    }
    return 1;
}

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("data.in","r",stdin);freopen("data.out","w",stdout);
    #endif
    n = read();
    m = read();
    for(int i = 1;i < n;i ++) add(i + 1,i,-1);
    for(int i = 1,pos,val;i <= m;i ++)
    {
        pos = read();
        val = read();
        laz[pos] += val;
        if(pos < n) add(pos + 1,pos,-laz[pos] + laz[pos + 1] - 1);
    }
    for(int i = 1;i <= n;i ++) add(n + 1,i,0);
    spfa();
    int mx = INF;
    for(int i = 1;i <= n;i ++) mx = min(mx,dis[i]);
    for(int i = 1;i <= n;i ++) ans += dis[i] - mx + 1;
    write(ans);ent;
    Blue_Archive;
}