Submission #1026315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026315		Unforgettablepl	Fish 2 (JOI22_fish2)	C++17	48 / 100	2215 ms	31060 KiB

fish2

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e15;

void strat1(int n,vector<int> arr,int q){
	vector<pair<int,int>> connection(n+1);
	vector<int> left(n+1),right(n+1);
	vector<long long> pref(n+2);
	vector<pair<int,int>> adj(n+1);
	auto solve = [&](int l,int r){
		pref[l-1]=0;
		for(int i=l;i<=r;i++){
			pref[i]=pref[i-1]+arr[i];
			adj[i].first=adj[i].second=0;
		}
		stack<pair<int,int>> s;
		s.emplace(INF,l-1);
		for(int i=l;i<=r;i++){
			while(s.top().first<=arr[i])s.pop();
			connection[i]=s.top();
			left[i]=s.top().second;
			s.emplace(arr[i],i);
		}
		while(!s.empty())s.pop();
		s.emplace(INF,r+1);
		for(int i=r;i>=l;i--){
			while(s.top().first<arr[i])s.pop();
			connection[i]=min(s.top(),connection[i]);
			right[i]=s.top().second;
			s.emplace(arr[i],i);
		}
		for(int i=l;i<=r;i++){
			if(connection[i].second<i)adj[connection[i].second].second=i;
			else adj[connection[i].second].first=i;		
		}
		int ans = 0;
		function<void(int,int)> dfs = [&](int x,int threshold){
			if(pref[right[x]-1]-pref[left[x]]<threshold)return;
			ans++;
			if(adj[x].first)dfs(adj[x].first,arr[x]);
			if(adj[x].second)dfs(adj[x].second,arr[x]);
		};
		dfs(adj[l-1].second,0);
		return ans;
	};
	for(int i=1;i<=q;i++){
		int type;cin>>type;
		if(type==1){
			int x,y;cin>>x>>y;
			arr[x]=y;
		} else {
			int l,r;cin>>l>>r;
			cout << solve(l,r) << '\n';
		}
	}
	exit(0);
}

struct node{
	int ele,cnt;
	node(int x=INT64_MIN):ele(x),cnt(1){}
	node(const node &a,const node &b):ele(max(a.ele,b.ele)),cnt(0){
		if(a.ele==ele)cnt+=a.cnt;
		if(b.ele==ele)cnt+=b.cnt;
	}
};

struct segtree{
	vector<node> tree;
	segtree():tree(262144){}
	void update(int k,int x){
		k+=131072;
		tree[k]=x;
		while(k/=2){
			tree[k]={tree[2*k],tree[2*k+1]};
		}
	}
	pair<int,int> get(int l,int r){
		node ans;l+=131072;r+=131072;
		while(l<=r){
			if(l&1)ans={ans,tree[l++]};
			if(r%2 == 0)ans={ans,tree[r--]};
			l/=2;r/=2;
		}
		return {ans.ele,ans.cnt};
	}
};

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<long long> arr(n+1);
	for(int i=1;i<=n;i++)cin>>arr[i];
	int q;
	cin >> q;
	if(q<=1000)strat1(n,arr,q);
	arr.emplace_back(0);
	arr[0]=arr[n+1]=INF;
	segtree cntranges;
	segtree sumtree;
	segtree sumtree2;
	vector<int> sums(n+2);
	vector<int> ranges(n+2);
	sums[0]=arr[0];
	for(int i=1;i<=n+1;i++)sums[i]=sums[i-1]+arr[i];
	{
		stack<pair<int,int>> s;
		s.emplace(arr[0],0);
		for(int i=1;i<=n;i++){
			while(s.top().first<arr[i])s.pop();
			if(sums[i-1]-sums[s.top().second] < arr[i]){
				ranges[s.top().second+1]++;
				ranges[i]--;
			}
			s.emplace(arr[i],i);
		}
	}
	{
		stack<pair<int,int>> s;
		s.emplace(arr[n+1],n+1);
		for(int i=n;i;i--){
			while(s.top().first<=arr[i])s.pop();
			if(sums[s.top().second-1]-sums[i] < arr[i]){
				ranges[i+1]++;
				ranges[s.top().second]--;
			}
			s.emplace(arr[i],i);
		}
	}
	for(int i=1;i<=n+1;i++)ranges[i]+=ranges[i-1];
	for(int i=1;i<=n;i++){
		cntranges.update(i,-ranges[i]);
		sumtree.update(i,arr[i]-sums[i-1]);
		sumtree2.update(i,arr[i]+sums[i]);
	}
	for(int i=1;i<=q;i++){
		int type;cin>>type;
		int l,r;cin>>l>>r;
		int ld = r;
		int rd = l;
		{
			// transform query
			for(int jump=65536;jump;jump/=2){
				if(ld-jump<l)continue;
				if(sumtree.get(ld-jump+1,r).first<=-sums[l-1])ld-=jump;
			}
			for(int jump=65536;jump;jump/=2){
				if(rd+jump>r)continue;
				if(sumtree2.get(l,rd+jump-1).first<=sums[r])rd+=jump;
			}
		}
		assert(ld<=rd);
		cout << cntranges.get(ld,rd).second << '\n';
	}
}

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