列表

详情

NC22363. Desperate … Fire Survive

描述

Rikka is running with her every cell to the hall where the contest will be held.
Well, EC Final is growing bigger and bigger... Thus more and more computers have been connected into the weak 2000W main wires. Heat is accumulating in every row.
When Rikka enters the hall, she finds LCR there rearranging the wires with the volunteers. However, the girl might not be able to do anything helpful but observing.
``Listen. We have no time to calculate parameters for the new circuit. Are you good at data structures? Help us, please...''
The circuitry is a sequence of n nodes, where there are m possible levels of nodes in total, numbered from 1 to m. Since a k-level node has a power limit twice of a (k-1)-level one, Rikka could merge two adjacent k-level nodes into a (k+1)-level one if k < m. She can also remove any node at any time from the circuitry while the order of rest nodes remains.
The volunteers have q queries in total. Each query contains a segment [l,r] and an integer level k. Rikka needs to count how many sub-segments of the assigned segment (i.e. a segment [x, y] such that ) can provide a k-level node, which means it is possible to turn circuitry sequence [x,y] into a single k-level node by merging adjacent nodes at the same level and removing nodes, where these two types of operations can be performed multiple times in any order. Notice that the level must be exactly k rather than higher or lower.

输入描述

The first line contains three integers , the length of the circuitry sequence, the maximal level and the number of queries, respectively.
The second line contains n integers , the levels of nodes in order.
Each of the following q lines contains three integers , describing a query.
Multiple integers in the same line are separated by spaces.

输出描述

Output q lines; each contains one integer, the answer to that query.

示例1

输入: 

5 5 5
1 1 1 1 1
1 5 1
1 5 2
1 5 3
1 5 4
1 5 5

输出: 

15
10
3
0
0

示例2

输入: 

5 5 5
4 3 2 1 1
1 5 1
1 5 2
1 5 3
1 5 4
1 5 5

输出: 

9
10
9
6
1

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 841ms, 内存消耗: 46724K, 提交时间: 2019-12-05 22:31:46 

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

#define pb push_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 2e5 + 70;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
const double eps = 1e-7;
const double PI = acos(-1.0);

int n, m, q;

int a[maxn];

vector<int> V[maxn];

vector<pii> F[maxn];

vector<ll> pre[maxn];

int f(int i, int j){
    if(i > n) return n+2;
    return upper_bound(ALL(F[j]),mp(i,INF))->second;
}

void add(int j, int e, int x){
    if(!F[j].size() || F[j].back().second != x) F[j].pb({e,x});
    F[j].back().first = e;
}

ll calc(int i, int j){
    if(!i) return 0;
    int p = upper_bound(ALL(F[j]),mp(i,INF)) - F[j].begin();
    return pre[j][p] - (ll)(F[j][p].first-i-1)*F[j][p].second;
}

ll query(int l, int r, int k){
    if(f(l,k) > r+1) return 0;
    int L = l, R = r;
    while(L < R){
        int M = L + (R - L + 1)/2;
        if(f(M,k) > r+1) R = M - 1;
        else L = M;
    }
    L = l;
    return (ll)(r+2)*(R-L+1) - (calc(R, k) - calc(L - 1, k));
}

int main(){
    //freopen("in.txt", "r", stdin);
    while(cin>>n>>m>>q){
        for(int i=1;i<=m;i++) V[i].clear(), F[i].clear(), pre[i].clear();
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            V[a[i]].pb(i);
        }

        for(int p:V[1]) F[1].pb({p+1, p+1});
        if(!F[1].size() || F[1].back().first != n+1) F[1].pb({n+1,n+2});

        for(int j=2;j<=m;j++){
            int ptr = 0, s = 1;
            for(int p:V[j]){
                while(ptr < F[j-1].size() && F[j-1][ptr].first-1 <= p){
                    int x = f(F[j-1][ptr].second, j-1);
                    add(j, F[j-1][ptr].first, min(p+1,x));
                    ptr++;
                }
                if(ptr == F[j-1].size()) break;
                int x = f(F[j-1][ptr].second, j-1);
                add(j, p+1, min(p+1, x));
                if(p+1 == F[j-1][ptr].first) ptr++;
            }
            while(ptr < F[j-1].size()){
                int x = f(F[j-1][ptr].second, j-1);
                add(j, F[j-1][ptr].first, x);
                ptr++;
            }
        }

        /*
        for(int j=1;j<=m;j++){
            cout<<"j: "<<j<<endl;
            for(int i=0;i<F[j].size();i++){
                printf("[%d,%d)=%d  ",i?F[j][i-1].first:1,F[j][i].first,F[j][i].second);
            }
            printf("\n");
        }
        */

        for(int j=1;j<=m;j++){
            for(int i=0;i<F[j].size();i++){
                if(!i) pre[j].pb((ll)(F[j][i].first-1)*F[j][i].second);
                else pre[j].pb(pre[j].back()+(ll)(F[j][i].first-F[j][i-1].first)*F[j][i].second);
            }
        }

        while(q--){
            int l, r, k; scanf("%d %d %d",&l,&r,&k);
            ll ans = query(l, r, k);
            printf("%lld\n", ans);
        }
    }
    return 0;
}

C++(clang++11) 解法, 执行用时: 476ms, 内存消耗: 30200K, 提交时间: 2021-05-08 22:19:31 

#include<bits/stdc++.h>
using namespace std;
#define MAXNUM 222222
#define rep(i,s,t) for(int i=s;i<t;i++)
typedef long long ll;
ll res[MAXNUM];
struct item {
	int l, r, id; 
	bool operator <(const item &a)const
	{
		return r < a.r;
	}
	item(int l,int r,int id):
		l(l),r(r),id(id)
	{}
};
bool cmp(const item &a, const item&b)
{
	return a.l < b.l;
}
namespace treea {
	ll tree[MAXNUM],tree2[MAXNUM];
	int tsize;
	int lowbit(int t)
	{
		return t & (-t);
	}

	void add(int x, ll y)
	{
		for (int i = x; i <= tsize; i += lowbit(i))
			tree[i] += y, tree2[i] += x * y;
	}
	ll getsum(int x)
	{
		ll res = 0,res2=0;
		for (int i = x; i > 0; i -= lowbit(i))
			res += tree[i], res2 += tree2[i];
		return res * (x + 1) - res2;
	}
}
vector<int> num[MAXNUM];
vector<item> q[MAXNUM],pos,tmp;

int main(void)
{
	int n, m, qq,a,b,c;
	scanf("%d%d%d", &n, &m, &qq);
	rep(i, 1, n + 1)
	{
		scanf("%d", &a);
		num[a].push_back(i);
	}
	rep(i, 1, qq + 1)
	{
		scanf("%d%d%d", &a, &b, &c);
		q[c].emplace_back(a, b, i);
	}
	treea::tsize = n;
	rep(i, 1, m + 1)
	{
		tmp.clear();
		int before = -1, nowi = -1;
		rep(i,0,pos.size())
		{
			while (nowi + 1 < i&&pos[nowi + 1].r <= pos[i].l - 1)
				nowi++;
			if (nowi != before)
				tmp.emplace_back(pos[nowi].l, pos[i].r, 1), before = nowi;
		}
		for (int k : num[i])
			tmp.emplace_back(k, k, -1);
		sort(tmp.begin(), tmp.end());
		int maxnum = 0;
		for (item &k : tmp)
			k.l = max(k.l, maxnum), maxnum = max(maxnum, k.l);
		pos.clear();
		pos = tmp,nowi = 0;
		sort(q[i].begin(), q[i].end());
		tmp.push_back({ n + 1,n + 1,-1 }), tmp.insert(tmp.begin(), { 0,0,1 });
		for (item &k : q[i])
		{
			while (tmp[nowi + 1].r <= k.r)
				treea::add(1, tmp[nowi + 1].r-tmp[nowi].r),
				treea::add(tmp[nowi].l + 1, -(tmp[nowi + 1].r-tmp[nowi].r)),nowi++;
			res[k.id] += treea::getsum(k.r)-treea::getsum(k.l-1);
			res[k.id] += max(0, k.r - tmp[nowi].r + 1)* 1LL *max(0, tmp[nowi].l - k.l + 1);
		}
		rep(i, 0, nowi)
			treea::add(1, -(tmp[i + 1].r - tmp[i].r)),
			treea::add(tmp[i].l + 1, tmp[i + 1].r - tmp[i].r);
	}
	rep(i, 1, qq + 1)
		printf("%lld\n", res[i]);
}

上一题

© 2024 nowcoder.com