列表

详情

NC26128. Segment Tree

描述

线段树(Segment tree)是一种二叉树形数据结构，用以存储区间或线段，并且允许快速查询结构内包含某一点的所有区间。——摘自维基百科

总之就是一种可以在很短的时间内对某个区间进行操作的数据结构。

小t精通线段树，熟知线段树的108种写法，例如单点更新单点查询最小值、单点更新单点查询最大值、单点更新单点查询总和、单点更新区间查询最小值、单点更新区间查询最大值、单点更新区间查询总和、区间增加区间查询最小值、区间增加区间查询最大值、区间增加区间查询总和、区间赋值区间查询最小值、区间赋值区间查询最大值、区间赋值区间查询总和、区间平方区间查询最小值、区间平方区间查询最大值、区间平方区间查询总和，……等等等等诸如此类，小t全都会。

为了提高队内线段树的平均姿势水平，小t专门出了一道线段树大杂烩来考考大家：

现在小t有一个整型数组int a[10000000]，初始值全为0。每次询问，小t会让你在数组中选择一个最靠近0下标的长度为n的全0区间，将这个区间的所有值更新成x。额外地，如果这个x在数组中已经存在，则小t会要求你把数组内所有值为x的数更新成0，同时不会再给出n。也就是说，小t的询问有时候会给出一个数，有时候会给出两个数，取决于具体的数组状态。

在对数组更新的同时，你需要回答被更新的区间起始下标、终止下标、数组的和、数组的最小值及数组的最大值。

输入描述

第一行输入一个正整数，代表询问个数

接下来q行，每行输入1~2个正整数，含义见题目描述。

题目保证

输出描述

对于每个询问输出一行，五个整数，依次代表被更新的区间起始下标、终止下标、数组的和、数组的最小值及数组的最大值。

示例1

输入: 

5
1 3
2 2
1
2
1 5

输出: 

0 2 3 1 1
3 4 7 1 2
0 2 4 2 2
3 4 0 0 0
0 4 5 1 1

说明:

第一次询问后，数组变成[1, 1, 1, 0, 0, ...]，更新了a[0]~a[2]的区间，\sum a_i=3，最小值和最大值都为1。

第二次询问后，数组变成[1, 1, 1, 2, 2, 0, 0, ...]，更新了最靠右的全0区间，即a[3]~a[4]的区间，\sum a_i=7，最小值为1，最大值为2。

第三次询问后，数组变成[0, 0, 0, 2, 2, 0, 0, ...]，a[0]~a[2]的区间被更新成0，\sum a_i变为4，最大值和最小值都为2。

第四次询问后，数组变成[0, 0, 0, ...]，a[3]~a[4]的区间被更新成0，\sum a_i=0，最大值和最小值也为0。

第五次询问后，数组变成[1, 1, 1, 1, 1, 0, 0, ...]，更新了a[0]~a[4]的区间，\sum a_i=5，最小值为1，最大值也为1。

原站题解

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

C++11(clang++ 3.9) 解法, 执行用时: 2020ms, 内存消耗: 4192K, 提交时间: 2019-06-08 17:01:34 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
 
set<pii>dat;
map<int,pii>MP;
 
void solve(){
    //MP[0]=pii(0,99999999);
    dat.insert(pii(0,9999999));
 
    ll sum=0;
    int Q;
    scanf("%d",&Q);
    while(Q--){
        int x;
        scanf("%d",&x);
        if(MP.count(x)){
            pii t=MP[x];
            printf("%d %d ",t.first,t.second);
            sum-=1LL*x*(t.second-t.first+1);
            MP.erase(x);
            printf("%lld ",sum);
            if(MP.size()) printf("%d %d\n",MP.begin()->first,(--MP.end())->first);
            else printf("0 0\n");
            auto it=dat.lower_bound(t);
            if(it!=dat.begin()){
                --it;
                if(it->second+1==t.first){
                    t.first=it->first;
                    dat.erase(it);
                }
            }
            it=dat.lower_bound(t);
            if(it->first-1==t.second){
                t.second=it->second;
                dat.erase(it);
            }
            dat.insert(t);
        }
        else{
            int n;
            scanf("%d",&n);
            sum+=1LL*x*n;
            for(auto P:dat){
                if(P.second-P.first+1>=n){
                    pii t=pii(P.first,P.first+n-1);
                    MP[x]=t;
                    printf("%d %d ",t.first,t.second);
                    printf("%lld ",sum);
                    printf("%d %d\n",MP.begin()->first,(--MP.end())->first);
                    dat.erase(P);
                    if(P.second-P.first+1>n){
                        dat.insert(pii(P.first+n,P.second));
                    }
                    break;
                }
            }
        }
    }
}
 
int main(){
 
    solve();
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 2100ms, 内存消耗: 4068K, 提交时间: 2019-06-08 15:26:32 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;

set<pii>dat;
map<int,pii>MP;

void solve(){
	//MP[0]=pii(0,99999999);
	dat.insert(pii(0,9999999));

	ll sum=0;
	int Q;
	scanf("%d",&Q);
	while(Q--){
		int x;
		scanf("%d",&x);
		if(MP.count(x)){
			pii t=MP[x];
			printf("%d %d ",t.first,t.second);
			sum-=1LL*x*(t.second-t.first+1);
			MP.erase(x);
			printf("%lld ",sum);
			if(MP.size()) printf("%d %d\n",MP.begin()->first,(--MP.end())->first);
			else printf("0 0\n");
			auto it=dat.lower_bound(t);
			if(it!=dat.begin()){
				--it;
				if(it->second+1==t.first){
					t.first=it->first;
					dat.erase(it);
				}
			}
			it=dat.lower_bound(t);
			if(it->first-1==t.second){
				t.second=it->second;
				dat.erase(it);
			}
			dat.insert(t);
		}
		else{
			int n;
			scanf("%d",&n);
			sum+=1LL*x*n;
			for(auto P:dat){
				if(P.second-P.first+1>=n){
					pii t=pii(P.first,P.first+n-1);
					MP[x]=t;
					printf("%d %d ",t.first,t.second);
					printf("%lld ",sum);
					printf("%d %d\n",MP.begin()->first,(--MP.end())->first);
					dat.erase(P);
					if(P.second-P.first+1>n){
						dat.insert(pii(P.first+n,P.second));
					}
					break;
				}
			}
		}
	}
}

int main(){

	solve();
    return 0;
}

上一题

© 2024 nowcoder.com