昨天写了一晚，越写复杂度越感觉不对，早上一想果然是假的。

(这里n,m,k我就不区分了)

首先一个城市的询问可以很容易的二分

check用树状数组维护区间(区间修改，单点查询的那种)

一次是\(O(nlog^2n)\)

n次就是\(O(n^2log^2n)\)

但是我们check的时候都是树状数组维护，询问相同

我们就可以整体二分(顾名思义)

把区间考虑成二叉树(类似线段树的形状)

我们每一层用一遍树状数组

查询的话，一个国家用一个链表存下所在的点

因为深度是\(logn\)的

复杂度是还是差不多的\((Onlog^2n)\)

妙啊

会炸long long 及时break就好

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define ll long longusing namespace std;const int N = 5e5+7;int read() { int x = 0,f = 1;char s = getchar(); for(; s > '9'||s < '0'; s = getchar()) if(s == '-') f = -1; for(; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0'; return x * f;}int n, m, k;int L[N], R[N], w[N], need[N], ans[N];pair
          
            erfen[N];vector
           
             hav[N];namespace BIT { ll sum[N]; void add(int id, ll ad) {for(int i = id; i <= m; i += (i&-i)) sum[i] += ad;} ll query(int id) {ll ans = 0;for(int i = id; i >= 1;i -= (i&-i)) ans += sum[i]; return ans;} void modify(int l, int r, ll ad) {add(l, ad), add(r + 1, -ad);} void clear() {memset(sum, 0, sizeof(sum));}}void solve() { vector
            
             
               > Q; for(int i = 1; i <= n; ++i) if(erfen[i].first!=k+1&&erfen[i].first <= erfen[i].second) Q.push_back(make_pair((erfen[i].first+erfen[i].second)>>1,i)); if(Q.empty()) return; sort(Q.begin(), Q.end()); BIT::clear(); for(int i = 1, js = 0;i <= k; ++ i) { if(L[i] <= R[i]) BIT::modify(L[i], R[i], (ll)w[i]); else BIT::modify(L[i], m, w[i]), BIT::modify(1, R[i], (ll)w[i]); while(js < Q.size() && Q[js].first == i) { int id = Q[js].second; ll tmp=0; for(vector
              
               ::iterator it = hav[id].begin();it != hav[id].end(); ++it) { tmp += BIT::query(*it); if(tmp>=(ll)need[id]) break; } if(tmp>=(ll)need[id]) ans[id] = i,erfen[id].second = i - 1; else erfen[id].first = i + 1; ++js; } } solve();}int main() { //read n = read(), m = read(); for(int i = 1; i <= m; ++i) { int x = read(); hav[x].push_back(i); } for(int i = 1; i <= n; ++i) need[i] = read(); k = read(); for(int i = 1; i <= k; ++i) L[i] = read(), R[i] = read(), w[i] = read(); for(int i = 1; i <= n; ++i) erfen[i].first = 1, erfen[i].second = k+1; //work solve(); //print for(int i = 1;i <= n; ++i) { if(ans[i]) printf("%d\n", ans[i]); else puts("NIE"); } return 0;}