MET-Meteors（整体二分）

MET-Meteors

我决定以后二分的 $m$都写成 $mid$！

题意：郁闷死了。。。写不动题意了！

思路：

1. 首先正常的读入以及连边，注意 $l>r$时将 $r$加上 $m$，即用两个连在一起的数组表示循环
2. 然后，怎么说呢？反正学会整体二分以后就感觉是板子题。。。
3. 考虑当前 $[l,r]$时间段的左半部分的流星雨全部落下后，将 $[x,y]$内的询问分成可以在左半部分完成的和不能在左半部分完成的；然后依次递归下去就好
4. 好像就没了，hhh

题面描述

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 3e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

struct P{
    int id, need;
}p[maxn], pp[maxn*2];

int n, m, k;
int head[maxn], to[maxn], nxt[maxn], tot;
int L[maxn], R[maxn], A[maxn], ans[maxn];
ll b[maxn*2];

inline void add_edge(int u, int v) {
    ++tot, to[tot]=v, nxt[tot]=head[u], head[u]=tot;
}

inline void update(int x, int d) { while(x<=2*m) b[x]+=d, x+=x&-x; }
inline ll qsum(int x) { ll ans=0; while(x) ans+=b[x], x-=x&-x; return ans; }

void solve(int l, int r, int x, int y) {
    if(l==r) {
        for(int i=x; i<=y; ++i) ans[p[i].id]=l;
        return;
    }
    int mid=(l+r)/2, cnt1=0, cnt2=n;
    for(int i=l; i<=mid; ++i) update(L[i],A[i]), update(R[i]+1,-A[i]);
    for(int j=x; j<=y; ++j) {
        ll tmp=0;
        for(int i=head[p[j].id]; i&&tmp<p[j].need; i=nxt[i]) {
            int v=to[i];
            tmp+=qsum(v)+qsum(v+m);
        }
        if(tmp>=p[j].need) pp[++cnt1]=p[j];
        else p[j].need-=tmp, pp[++cnt2]=p[j];
    }
    for(int i=l; i<=mid; ++i) update(L[i],-A[i]), update(R[i]+1,A[i]);
    for(int i=1; i<=cnt1; ++i) p[x+i-1]=pp[i];
    for(int i=n+1; i<=cnt2; ++i) p[x+cnt1+i-n-1]=pp[i];
    solve(l,mid,x,x+cnt1-1), solve(mid+1,r,x+cnt1,y);
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    n=read(), m=read();
    for(int i=1; i<=m; ++i) add_edge(read(),i);
    for(int i=1; i<=n; ++i) p[i]=(P){i,read()};
    k=read();
    for(int i=1; i<=k; ++i) {
        L[i]=read(), R[i]=read(), A[i]=read();
        if(R[i]<L[i]) R[i]+=m;
    }
    solve(1,k+1,1,n);
    for(int i=1; i<=n; ++i) ans[i]==k+1?printf("NIE\n"):printf("%d\n", ans[i]);
}