(Codeforces) 786B. Legacy

http://codeforces.com/contest/786/problem/B

超酷的最短路徑題

要在上面建線段樹><

詳細看editorial吧

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
using namespace std;

#define LL   long long
#define ld   long double
#define pii  pair<int,int>
#define pLL  pair<LL,LL>
#define vint vector<int>
#define vLL  vector<LL>

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e));
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e),(f));

#define Pi1(x) printf("%d",  (x));
#define PL1(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)
#define REP(L,R,k) for (int i = (L); (R) >= i; i+= (k) )

int myRnd(int L,int R) {
    return abs(( (rand()<<15)|rand() ) ) % (R-L+1) + L;
}

#define vpii vector<pii>

struct Dijkstra {
    static const int N = 2e6 +6;
    vpii G[N];
    int n,s;
    void init(int n,int s) {
        this->n = n;
        this->s = s;
        REP0(i,n+1) {
            G[i].clear();
        }
    }
    void add_edge(int from,int to,int cost) {
        G[from].PB({to,cost});
    }
    LL d[N];
    static const LL INF = 1e17 + 6;
    void solve() {
        REP0(i,n+1)
        {
            d[i] = INF;
        }
        d[s]=0;
        priority_queue<pLL,vector<pLL>,greater<pLL> > pq;
        pq.push({d[s],s});
        while (!pq.empty()) {
            pLL p= pq.top();
            pq.pop();
            if (d[p.S] != p.F) continue;
            for (pii pp:G[p.S]) {
                if (d[pp.F] > d[p.S] + pp.S) {
                    d[pp.F] = d[p.S] + pp.S;
                    pq.push({d[pp.F],pp.F});
                }
            }
        }
    }
} dijkstra;

const int N = 2e6 + 6;

int lc[N],rc[N];
int cnt;

void build1(int now,int L,int R) {
    if (L==R) {
        lc[now] = rc[now] = -1;
        dijkstra.add_edge(now,L,0);
        return;
    }
    int mid=(L+R)>>1;
    lc[now] = cnt++;
    rc[now] = cnt++;
    dijkstra.add_edge(now,lc[now],0);
    dijkstra.add_edge(now,rc[now],0);
    build1(lc[now],L,mid);
    build1(rc[now],mid+1,R);
}

void build2(int now,int L,int R,int par) {
    if (par != now) dijkstra.add_edge(now,par,0);
    if (L==R) {
        dijkstra.add_edge(L,now,0);
        lc[now] = rc[now] = -1;
        return;
    }
    int mid=(L+R)>>1;
    lc[now] = cnt++;
    rc[now] = cnt++;
    build2(lc[now],L,mid,now);
    build2(rc[now],mid+1,R,now);
    return;
}

void query1(int now,int L,int R,int l,int r,int v,int w) {
    if (L > r || l > R) return;
    else if (l<= L && R<=r) {
        dijkstra.add_edge(v,now,w);
        return;
    }
    int mid = (L+R)>>1;
    query1(lc[now],L,mid,l,r,v,w);
    query1(rc[now],mid+1,R,l,r,v,w);
}

void query2(int now,int L,int R,int l,int r,int v,int w) {
    if (L > r || l > R) return;
    else if (l<= L && R<=r) {
        dijkstra.add_edge(now,v,w);
        return;
    }
    int mid = (L+R)>>1;
    query2(lc[now],L,mid,l,r,v,w);
    query2(rc[now],mid+1,R,l,r,v,w);
}

int main () {
    srand(time(NULL));
    int n,q,s;
    Siii(n,q,s);
    dijkstra.init(N-1,s);
    cnt = n+1;
    int root1=cnt++;
    build1(root1,1,n);
    int root2=cnt++;
    build2(root2,1,n,root2);
    REP1(i,q)
    {
        int type;
        Si(type);
        if (type == 1) {
            int u,v,w;
            Siii(u,v,w);
            dijkstra.add_edge(u,v,w);
        }
        else if (type == 2) {
            int v,l,r,w;
            Siiii(v,l,r,w);
            query1(root1,1,n,l,r,v,w);
        }
        else if (type == 3) {
            int v,l,r,w;
            Siiii(v,l,r,w);
            query2(root2,1,n,l,r,v,w);
        }
    }
    dijkstra.solve();
    REP1(i,n) {
        LL val=dijkstra.d[i];
        if (i!=1) Pspace;
        if (val == dijkstra.INF) Pi1(-1)
        else PL1(val);
    }
    Pendl;
}

(POJ) K-th Number [靜態第K大] [整體二分]

http://poj.org/problem?id=2104

法一：可持久化線段樹 + 二分搜

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 1e5 + 6;
const int MAX_P = 22*MAX_N;
const int INF = 1e9 + 7;

struct Node {
    static Node mem[MAX_P];
    Node *lc,*rc;
    int val;
    Node() {
        lc=rc=NULL;
        val=0;
    }
    void pull() {
        val = lc->val + rc->val;
    }
} Node::mem[MAX_P],*ptr=Node::mem;

Node *getNode(Node* node) {
    Node* tmp=new(ptr++)Node();
    tmp->val = node->val;
    tmp->lc = node->lc;
    tmp->rc=node->rc;
    return tmp;
}

Node* Build(int L,int R) {
    Node* node = new (ptr++)Node();
    if (L==R) {
        return node;
    }
    int mid=(L+R)>>1;
    node->lc=Build(L,mid);
    node->rc=Build(mid+1,R);
    return node;
}

void modify(Node* pre,Node* now,int L,int R,int pos,int val) {
    if (L==R) {
        now->val += val;
        return;
    }
    int mid=(L+R)>>1;
    if (pos<=mid) {
        now->lc = getNode(pre->lc);
        modify(pre->lc,now->lc,L,mid,pos,val);
    }
    else {
        now->rc = getNode(pre->rc);
        modify(pre->rc,now->rc,mid+1,R,pos,val);
    }
    now->pull();
}

int query(Node* node,int L,int R,int l,int r) {
    if (l>R || L>r) return 0;
    else if (l<=L && R<=r) return node->val;
    int mid=(L+R)>>1;
    return query(node->lc,L,mid,l,r) + query(node->rc,mid+1,R,l,r);
}

int a[MAX_N];
Node *root[MAX_N];

int main () {
    
        int n,q;
        scanf("%d %d",&n,&q);
        vector<int> v;
        v.push_back(-INF);
        for (int i=1;n>=i;i++) {
            scanf("%d",&a[i]);
            v.push_back(a[i]);
        }
        sort(v.begin(),v.end());
        v.resize(unique(v.begin(),v.end()) - v.begin());
        int m=v.size()-1;
        root[0] = Build(1,n);
        for (int i=1;n>=i;i++) {
            a[i] = lower_bound(v.begin(),v.end(),a[i]) - v.begin();
            root[i] = getNode(root[i-1]);
            modify(root[i-1],root[i],1,m,a[i],1);
        }
        while (q--) {
            int x,y,z;
            scanf("%d %d %d",&x,&y,&z);
            x--;
            int L=0,R=m+1;
            while (R-L > 1) {
                int mid=(L+R)>>1;
                if (query(root[y],1,m,1,mid) - query(root[x],1,m,1,mid) < z) L=mid;
                else R=mid;
            }
            printf("%d\n",v[R]);
        }
        ptr = Node::mem;
    
}

法二：可持久化線段樹

延續上一種作法，發現，可以一次遞迴兩顆線段樹，不用再特別寫二分搜XD

code provided by boook

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define REP(i,j,k)     for(int i = j ; i < k ; ++i)
#define RREP(i,j,k)    for(int i = j ; i >=k ; --i)
#define A    first
#define B    second
#define mp   make_pair
#define pb   push_back
#define PII pair<int , int>
#define MEM(i,j)   memset(i , j , sizeof i)
#define ALL(i)     i.begin() , i.end()
#define DBGG(i,j)     cout << i << " " << j << endl
#define DB4(i,j,k,l)  cout << i << " " << j << " " << k << " " << l << endl
#define IOS cin.tie() , cout.sync_with_stdio(0)
#define endl "\n"
///------------------------------------------------------------
#define MAX 100900
#define INF 0x3f3f3f3f
#define mid ((l + r) >> 1)
 
int sum[MAX * 20] , ls[MAX * 20] , rs[MAX * 20] , root[MAX * 20] , po = 2;
int n , m , x[MAX];
void Copy(int now , int dot){
    sum[now] = sum[dot];
    ls[now] = ls[dot];
    rs[now] = rs[dot];
}
int update(int dot , int l , int r , int val){
    int now = po ++;
    Copy(now , dot);
    if(l == val && r == val) return sum[now] ++ , now;
    else {
        if(val <= mid + 0) ls[now] = update(ls[now] , l , mid + 0 , val);
        if(mid + 1 <= val) rs[now] = update(rs[now] , mid + 1 , r , val);
        sum[now] = sum[ls[now]] + sum[rs[now]];
        return now;
    }
}
int query(int r1 , int r2 , int l , int r , int k){
    if(l == r) return l;
    else{
        int lsum = sum[ls[r2]] - sum[ls[r1]];
        if(k <= lsum) return query(ls[r1] , ls[r2] , l , mid + 0 , k);
        else          return query(rs[r1] , rs[r2] , mid + 1 , r , k - lsum);
    }
}
int main(){
    IOS;
    while(cin >> n >> m){
        vector<int> uni;
        REP(i , 1 , n + 1) cin >> x[i];
        REP(i , 1 , n + 1) uni.pb(x[i]);
        sort(ALL(uni));
        uni.resize(unique(ALL(uni)) - uni.begin());
        REP(i , 1 , n + 1) x[i] = lower_bound(ALL(uni) , x[i]) - uni.begin();
        root[0] = 1 , po = 2;
        REP(i , 1 , n + 1){
            root[i] = update(root[i - 1] , 0 , n , x[i]);
        }
        REP(i , 1 , m + 1){
            int l , r , k;
            cin >> l >> r >> k;
            cout << uni[query(root[l - 1] , root[r] , 0 , n , k)] << endl;
        }
    }
    return 0;
}

法三：整體二分( N (lg N)^2 版本 )

模板略~

const int N = 1e5 + 6;

struct BIT {
    int n;
    int a[N];
    void init(int n) {
        this->n = n;
        MEM0(a);
    }
    void add(int pos,int val) {
        for (int i=pos;n>=i;i+=i&(-i)) {
            a[i] += val;
        }
    }
    int qry(int pos) {
        int ret=0;
        for (int i=pos;i>=1;i-=i&(-i)) {
            ret += a[i];
        }
        return ret;
    }
    int query(int L,int R) {
        return qry(R) - qry(L-1);
    }
} bit;

int n,q;

vector<int> v;
int ans[N];
int a[N];

int qL[N],qR[N],qK[N];
vint pos[N];

void do_things(int L,int mid) {
    for (int i=L;mid>=i;i++) {
        for (int j=0;SZ(pos[i])>j;j++) {
            int p=pos[i][j];
            bit.add(p,1);
        }
    }
}

void undo_things(int L,int mid) {
    for (int i=L;mid>=i;i++) {
        for (int j=0;SZ(pos[i])>j;j++) {
            int p=pos[i][j];
            bit.add(p,-1);
        }
    }
}

void split(int mid,vint &queries,vint &ok,vint &notok) {
    for (int i=0;SZ(queries)>i;i++) {
        int qid=queries[i];
        if (bit.query(qL[qid],qR[qid]) >= qK[qid]) {
            ok.PB(qid);
        }
        else {
            notok.PB(qid);
        }
    }
    vector<int> ().swap(queries);
}

void totBS(int L,int R,vint queries) {
    //cout<<"l = "<<L<<" , r = "<<R<<endl;
    if (L==R) {
        do_things(L,L);
        for (int i=0;SZ(queries)>i;i++) {
            int qid=queries[i];
            ans[qid] = L;
        }
        return;
    }
    int mid=(L+R)>>1;
    do_things(L,mid);
    vint ok,notok;
    split(mid,queries,ok,notok);
    undo_things(L,mid);
    totBS(L,mid,ok);
    totBS(mid+1,R,notok);
}

int main () {
    srand(time(NULL));
    Sii(n,q);
    REP1(i,n) {
        Si(a[i]);
        v.PB(a[i]);
    }
    sort(ALL(v));
    v.resize(unique(ALL(v))-v.begin());
    bit.init(SZ(v));
    REP1(i,n) {
        a[i] = lower_bound(ALL(v),a[i])-v.begin()+1;
        pos[ a[i] ].PB(i);
    }
    vint Q;
    REP1(i,q) {
        Siii(qL[i],qR[i],qK[i]);
        Q.PB(i);
    }
    MEM1(ans);
    totBS(1,SZ(v),Q);
    REP1(i,q) {
        Pi(v[ans[i]-1]);
    }
}

法四：整體二分 (用特殊技巧壓到 N lg N)

這份可能是因為vector用太多吧，跑起來比方法三的時間要多一倍><

模板略~

const int N = 1e5 + 6;

int a[N];
int qL[N],qR[N],qK[N];
int ans[N];

#define vpii vector<pii>

//( val_L , i )

LL sum[N];

void totBS(int L,int R,vint e,vpii vqL,vpii vqR) {
    //cout<<"L = "<<L<<" , R = "<<R<<" ,sze = "<<SZ(e)<<" , szvqL = "<<SZ(vqL)<<endl;
    if (L==R) {
        for (int i=0;SZ(vqL)>i;i++) {
            pii p=vqL[i];
            ans[p.S] = L;
        }
        return;
    }
    vint re,le;
    vpii rvqL,lvqL;
    vpii rvqR,lvqR;
    int mid = (L+R)>>1;
    int vqLid=0,vqRid = 0;
    int cnt=0;
    for (int i=0;SZ(e)>i;i++) {
        int ee=e[i];
        if (a[ee] <= mid) {
            le.PB(ee);
            while (vqLid < SZ(vqL) && qL[ vqL[vqLid].S ] <= ee) sum[ vqL[vqLid++].S ] -= cnt;
            while (vqRid < SZ(vqR) && qR[ vqR[vqRid].S ] <  ee) sum[ vqR[vqRid++].S ] += cnt;
            cnt++;
        }
        else {
            re.PB(ee);
        }
    }
    while (vqLid < SZ(vqL)) sum[ vqL[vqLid++].S ] -= cnt;
    while (vqRid < SZ(vqR)) sum[ vqR[vqRid++].S ] += cnt;
    for (int i=0;SZ(vqL) > i;i++) {
        pii ii=vqL[i];
        if (qK[ii.S] <= sum[ii.S]) {
            lvqL.PB(ii);
        }
        else {
            rvqL.PB(ii);
        }
    }
    for (int i=0;SZ(vqR) > i;i++) {
        pii ii=vqR[i];
        if (qK[ii.S] <= sum[ii.S]) {
            lvqR.PB(ii);
        }
        else {
            rvqR.PB(ii);
            qK[ii.S] -= sum[ii.S];
        }
        sum[ii.S] = 0;
    }
    vint ().swap(e);
    vpii ().swap(vqL);
    vpii ().swap(vqR);
    totBS(L,mid+0,le,lvqL,lvqR);
    totBS(mid+1,R,re,rvqL,rvqR);
}

int main () {
    srand(time(NULL));
    int n,m;
    Sii(n,m);
    vint v;
    REP1(i,n)
    {
        Si(a[i]);
        v.PB(a[i]);
    }
    sort(ALL(v));
    v.resize(unique(ALL(v))-v.begin());
    vint e;
    REP1(i,n)
    {
        a[i] = lower_bound(ALL(v),a[i])-v.begin();
        e.PB(i);
    }
    vpii vqL,vqR;
    REP1(i,m)
    {
        Siii(qL[i],qR[i],qK[i]);
        vqL.PB(MP(qL[i],i));
        vqR.PB(MP(qR[i],i));
    }
    sort(ALL(vqL));
    sort(ALL(vqR));
    totBS(0,SZ(v)-1,e,vqL,vqR);
    REP1(i,m)
    {
        Pi(v[ans[i]]);
    }
}

(POI) XVIII OI Meteors [整體二分]

https://szkopul.edu.pl/problemset/problem/7JrCYZ7LhEK4nBR5zbAXpcmM/site/?key=statement

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
using namespace std;

#define LL   long long
#define ld   long double
#define pii  pair<int,int>
#define pLL  pair<LL,LL>
#define vint vector<int>
#define vLL  vector<LL>

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e));
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e),(f));

#define Pi1(x) printf("%d",  (x));
#define PiL(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)
#define REP(L,R,k) for (int i = (L); (R) >= i; i+= (k) )

int myRnd(int L,int R) {
    return abs(( (rand()<<15)|rand() ) ) % (R-L+1) + L;
}

const int N = 3e5 + 6;

struct BIT {
    int n;
    LL a[N];
    void init(int n) {
        this->n = n;
        MEM0(a);
    }
    void add(int pos,int val) {
        for (int i=pos;n>=i;i+=i&(-i)) {
            a[i] += val;
        }
    }
    LL qry(int pos) {
        LL ret=0;
        for (int i=pos;i>=1;i-=i&(-i)) {
            ret += a[i];
        }
        return ret;
    }
    LL query(int L,int R) {
        return qry(R) - qry(L-1);
    }
} bit;

int owner[N];
int goal[N];
int n,m;
int qL[N],qR[N],qX[N];
vint has_land[N];

void do_things(int L,int mid) {
    for (int i=L;mid>=i;i++) {
        //cout<<"i = "<<i<<endl;
        int nl=qL[i],nr = qR[i];
        int nx=qX[i];
        //cout<<"nl = "<<nl<<" , nr = "<<nr<<" , nx = "<<nx<<endl;
        if (nr >= nl) {
            bit.add(nl,nx);
            bit.add(nr+1,-nx);
        }
        else if (nl > nr) {
            bit.add(1,nx);
            bit.add(nr+1,-nx);
            bit.add(nl,nx);
            bit.add(m+1,-nx);
        }

    }
}

void undo_things(int L,int mid) {
    for (int i=L;mid>=i;i++) {
        int nl=qL[i],nr = qR[i];
        int nx=qX[i];
        bit.add(nl,-nx);
        bit.add(nr+1,nx);
        if (nl > nr) {
            bit.add(1,-nx);
            //bit.add(m+1,-nx);
        }
    }
}

LL tmp[N];
int ans[N];

void split(int mid,vint& persons,vint &ok,vint &notok) {
    //cout<<"mid = "<<mid<<endl;
    for (int p:persons) {
        tmp[p] = 0;
        for (int it:has_land[p]) {
            tmp[p] += bit.qry(it);
            //cout<<"it = "<<it<< " , query = "<<bit.qry(it)<<endl;
            if (tmp[p] >= goal[p]) break;
        }
        if (tmp[p] >= goal[p]) {
            ok.PB(p);
            if (ans[p] > 0) {
                ans[p] = min(ans[p],mid);
            }
            else {
                ans[p] = mid;
            }
        }
        else {
            goal[p] -= tmp[p];
            notok.PB(p);
        }
    }
    //cout<<"after mid , ok : ";for(int i:ok) cout<<i<<' ';cout<<" , notok : ";for (int i:notok)cout<<i<<' ';
    //cout<<endl;
    vector<int> ().swap(persons);  //release memory
}

void totBS(int L,int R,vint persons) {
    //cout<<"L = "<<L<<" , R =  "<<R<<endl;
    if (L > R || SZ(persons) == 0) return;
    int mid =(L+R) >> 1;
    //cout<<"mid = "<<mid<<endl;
    do_things(L,mid);
    vint ok,notok;
    split(mid,persons,ok,notok);
    undo_things(L,mid);
    totBS(L,mid-1,ok);
    totBS(mid+1,R,notok);
}

int main () {
    //srand(time(NULL));
    Sii(n,m);
    bit.init(m+1);
    REP1(i,m) {
        Si(owner[i]);
        has_land[ owner[i] ].PB(i);
    }
    REP1(i,n) {
        Si(goal[i]);
    }
    int k;
    Si(k);
    REP1(i,k) {
        Siii(qL[i],qR[i],qX[i]);
    }
    vint persons;
    REP1(i,n) persons.PB(i);
    totBS(1,k,persons);
    REP1(i,n) {
        //cout<<"I = "<<i<<" , goal = "<<goal[i]<<endl;
        if (ans[i] == 0) puts("NIE");
        else Pi(ans[i]);
    }
}