Submission #966272

#	Time	Username	Problem	Language	Result	Execution time	Memory
966272		huutuan	Fish 2 (JOI22_fish2)	C++14	100 / 100	672 ms	69612 KiB

fish2

#include<bits/stdc++.h>

using namespace std;

#define int long long

struct Range{
   int sum;
   int cnt;
   int block;
   Range (int _sum=0, int _cnt=0, int _block=0){
      sum=_sum, cnt=_cnt, block=_block;
   }
};

const int N=1e5+10, LG=32, inf=1e18;
vector<Range> pf_q1, pf_q2, sf_q1, sf_q2;

struct Node{
   vector<Range> pf, sf;
   int cnt;
   int sum;
   int l, r, lval, rval;
   Node (){
      pf.reserve(LG);
      sf.reserve(LG);
      cnt=sum=0;
      l=1, r=0;
   }
   void merge(Node &tl, Node &tr){
      pf=tl.pf;
      sf=tr.sf;
      pf.pop_back();
      sf.pop_back();
      if (tl.sum==0){
         (*this)=tr;
         return;
      }
      if (tr.sum==0){
         (*this)=tl;
         return;
      }
      l=tl.l, r=tr.r, lval=tl.lval, rval=tr.rval;
      sum=tl.sum+tr.sum;
      cnt=0;
      pf_q1.clear();
      pf_q2.clear();
      sf_q1.clear();
      sf_q2.clear();
      for (int _i=1, j=0; _i<=(int)tl.sf.size(); ++_i){
         int i=_i;
         int curl=(i?tl.sf[i-1].sum:0);
         int curr=(j?tr.pf[j-1].sum:0);
         int cur;
         int _block=0;
         while (1){
            bool stop=true;
            while (j<(int)tr.pf.size()){
               cur=curl+curr;
               int block=j?tr.pf[j-1].block:tr.lval;
               if (cur<block){
                  _block=block;
                  break;
               }
               stop=false;
               curr=tr.pf[j++].sum;
            }
            while (i<(int)tl.sf.size()){
               cur=curl+curr;
               int block=i?tl.sf[i-1].block:tl.rval;
               if (cur<block){
                  _block=block;
                  break;
               }
               stop=false;
               curl=tl.sf[i++].sum;
            }
            if (stop) break;
         }
         if (i==(int)tl.sf.size() && j==(int)tr.pf.size()){
            cnt+=tl.sf[_i-1].cnt;
         }else if (i==(int)tl.sf.size()){
            pf_q1.emplace_back(cur, tl.sf[_i-1].cnt, _block);
         }else if (j==(int)tr.pf.size()){
            sf_q1.emplace_back(cur, tl.sf[_i-1].cnt, _block);
         }
      }
      for (int _j=1, i=0; _j<=(int)tr.pf.size(); ++_j){
         int j=_j;
         int curl=(i?tl.sf[i-1].sum:0);
         int curr=(j?tr.pf[j-1].sum:0);
         int cur;
         int _block=0;
         while (1){
            bool stop=true;
            while (j<(int)tr.pf.size()){
               cur=curl+curr;
               int block=j?tr.pf[j-1].block:tr.lval;
               if (cur<block){
                  _block=block;
                  break;
               }
               stop=false;
               curr=tr.pf[j++].sum;
            }
            while (i<(int)tl.sf.size()){
               cur=curl+curr;
               int block=i?tl.sf[i-1].block:tl.rval;
               if (cur<block){
                  _block=block;
                  break;
               }
               stop=false;
               curl=tl.sf[i++].sum;
            }
            if (stop) break;
         }
         if (i==(int)tl.sf.size() && j==(int)tr.pf.size()){
            cnt+=tr.pf[_j-1].cnt;
         }else if (i==(int)tl.sf.size()){
            pf_q2.emplace_back(cur, tr.pf[_j-1].cnt, _block);
         }else if (j==(int)tr.pf.size()){
            sf_q2.emplace_back(cur, tr.pf[_j-1].cnt, _block);
         }
      }
      int i1=0, i2=0;
      while (i1<(int)pf_q1.size() && i2<(int)pf_q2.size()){
         if (pf_q1[i1].sum<=pf_q2[i2].sum){
            if (pf.size() && pf.back().sum==pf_q1[i1].sum) pf.back().cnt+=pf_q1[i1].cnt;
            else pf.push_back(pf_q1[i1]);
            ++i1;
         }else{
            if (pf.size() && pf.back().sum==pf_q2[i2].sum) pf.back().cnt+=pf_q2[i2].cnt;
            else pf.push_back(pf_q2[i2]);
            ++i2;
         }
      }
      while (i1<(int)pf_q1.size()){
         if (pf.size() && pf.back().sum==pf_q1[i1].sum) pf.back().cnt+=pf_q1[i1].cnt;
         else pf.push_back(pf_q1[i1]);
         ++i1;
      }
      while (i2<(int)pf_q2.size()){
         if (pf.size() && pf.back().sum==pf_q2[i2].sum) pf.back().cnt+=pf_q2[i2].cnt;
         else pf.push_back(pf_q2[i2]);
         ++i2;
      }
      i1=0, i2=0;
      while (i1<(int)sf_q1.size() && i2<(int)sf_q2.size()){
         if (sf_q1[i1].sum<=sf_q2[i2].sum){
            if (sf.size() && sf.back().sum==sf_q1[i1].sum) sf.back().cnt+=sf_q1[i1].cnt;
            else sf.push_back(sf_q1[i1]);
            ++i1;
         }else{
            if (sf.size() && sf.back().sum==sf_q2[i2].sum) sf.back().cnt+=sf_q2[i2].cnt;
            else sf.push_back(sf_q2[i2]);
            ++i2;
         }
      }
      while (i1<(int)sf_q1.size()){
         if (sf.size() && sf.back().sum==sf_q1[i1].sum) sf.back().cnt+=sf_q1[i1].cnt;
         else sf.push_back(sf_q1[i1]);
         ++i1;
      }
      while (i2<(int)sf_q2.size()){
         if (sf.size() && sf.back().sum==sf_q2[i2].sum) sf.back().cnt+=sf_q2[i2].cnt;
         else sf.push_back(sf_q2[i2]);
         ++i2;
      }
      pf.emplace_back(sum, cnt, inf);
      sf.emplace_back(sum, cnt, inf);
   }
};

struct SegmentTree{
   int n;
   vector<Node> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, Node());
   }
   void build(int k, int l, int r, int *a){
      if (l==r){
         t[k].cnt=1;
         t[k].sum=a[l];
         t[k].l=t[k].r=l;
         t[k].lval=t[k].rval=a[l];
         t[k].pf.clear();
         t[k].sf.clear();
         t[k].pf.emplace_back(a[l], 1, inf);
         t[k].sf.emplace_back(a[l], 1, inf);
         return;
      }
      int mid=(l+r)>>1;
      build(k<<1, l, mid, a);
      build(k<<1|1, mid+1, r, a);
      t[k].merge(t[k<<1], t[k<<1|1]);
   }
   void update(int k, int l, int r, int pos, int val){
      if (l==r){
         t[k].cnt=1;
         t[k].sum=t[k].lval=t[k].rval=val;
         t[k].pf.clear();
         t[k].sf.clear();
         t[k].pf.emplace_back(val, 1, inf);
         t[k].sf.emplace_back(val, 1, inf);
         return;
      }
      int mid=(l+r)>>1;
      if (pos<=mid) update(k<<1, l, mid, pos, val);
      else update(k<<1|1, mid+1, r, pos, val);
      t[k].merge(t[k<<1], t[k<<1|1]);
   }
   Node ans, ans2;
   void get(int k, int l, int r, int L, int R){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         ans.merge(ans2, t[k]);
         ans2=ans;
         return;
      }
      int mid=(l+r)>>1;
      get(k<<1, l, mid, L, R);
      get(k<<1|1, mid+1, r, L, R);
   }
} st;

int n, q, a[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   for (int i=1; i<=n; ++i) cin >> a[i];
   st.init(n);
   st.build(1, 1, n, a);
   cin >> q;
   while (q--){
      int type; cin >> type;
      if (type==1){
         int x, y; cin >> x >> y;
         st.update(1, 1, n, x, y);
      }else{
         int l, r; cin >> l >> r;
         st.ans=Node(); st.ans2=Node();
         st.get(1, 1, n, l, r);
         cout << st.ans.cnt << '\n';
      }
   }
   return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 17 / 17