#define maxn 2000000 #define max(x, y) (x) > (y) ? (x) : (y) #define min(x, y) (x) < (y) ? (x) : (y) struct tree { long long ml, mr, x, left; }t[maxn * 2 + 1]; long long n, m; inline long long read() { long long x=0,p=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-')p=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*p; } long long tot = 0; long long make(long long p, long long l, long long r) { if (l == r) { t[p].ml = t[p].mr = t[p].x = l; return 0; } long long m = (l + r) >> 1; make(p << 1, l, m); make(p << 1 | 1, m + 1, r); t[p].ml = min(t[p << 1].ml, t[p << 1 | 1].ml); t[p].mr = max(t[p << 1].mr, t[p << 1 | 1].mr); t[p].x = t[p << 1].x + t[p << 1 | 1].x; } long long count(long long p, long long l, long long r, long long x, long long y, long long right) { long long m = (l + r) >> 1; if (right <= t[p].ml) return 0; if (l == r) { if (right <= t[p].mr) return 0; t[p].ml = right; t[p].mr = right; long long ans = right - t[p].x; t[p].x = right; return ans; } if (right < t[p].mr) { long long ans = t[p].left; if (ans) { t[p << 1].left = t[p << 1 | 1].left = ans; t[p].left = 0; t[p << 1].x = (m - l + 1) * ans; t[p << 1 | 1].x = (r - (m + 1) + 1) * ans; t[p << 1].ml = t[p << 1 | 1].ml = t[p << 1].mr = t[p << 1 | 1].mr = ans; } if (y <= m) ans = count(p << 1, l, m, x, y,right); else if (x > m) ans = count(p << 1 | 1, m + 1, r, x, y, right); else ans = count(p << 1, l, m, x, m, right) + count(p << 1 | 1, m + 1, r, m + 1, y, right); t[p].ml = min(t[p << 1].ml, t[p << 1 | 1].ml); t[p].mr = max(t[p << 1].mr, t[p << 1 | 1].mr); t[p].x = t[p << 1].x + t[p << 1 | 1].x; return ans; } else { if (l == x && r == y) { t[p].left = t[p].ml = t[p].mr = right; long long ans = t[p].x; t[p].x = right * (r - l + 1); return t[p].x - ans; } else { long long ans = t[p].left; if (ans) { t[p << 1].left = t[p << 1 | 1].left = ans; t[p].left = 0; t[p << 1].x = (m - l + 1) * ans; t[p << 1 | 1].x = (r - (m + 1) + 1) * ans; t[p << 1].ml = t[p << 1 | 1].ml = t[p << 1].mr = t[p << 1 | 1].mr = ans; } if (y <= m) ans = count(p << 1, l, m, x, y,right); else if (x > m) ans = count(p << 1 | 1, m + 1, r, x, y, right); else ans = count(p << 1, l, m, x, m, right) + count(p << 1 | 1, m + 1, r, m + 1, y, right); t[p].ml = min(t[p << 1].ml, t[p << 1 | 1].ml); t[p].mr = max(t[p << 1].mr, t[p << 1 | 1].mr); t[p].x = t[p << 1].x + t[p << 1 | 1].x; return ans; } } } int main() { freopen("ohmygod.in", "r", stdin); freopen("ohmygod.out", "w", stdout); n = read(); m = read(); make(1, 1, n); for (long long i = 1; i <= m; i++) { long long x = read(), y = read(); printf("%lld\n", count(1, 1, n, x, y, y)); } } ```]]>