列表

详情


NC25548. 温暖的签到题

描述

给你一个长度为n的序列,初始为1,2,3...n,对其进行m次操作。
操作有两种:
1 l r  表示将区间[l,r]用 [1,2...r-l+1] 覆盖
2 l r 查询[l,r]的区间和

输入描述

第一行包含2个数字,n,m(1 <= n,m <= 1e5)

接下来包含m行,格式如题面所示

输出描述

对于每个操作2,输出一行一个整数表示答案

示例1

输入:

10 5
2 1 10
1 3 6
2 1 10
1 1 10
2 1 10

输出:

55
47
55

原站题解

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

C++14(g++5.4) 解法, 执行用时: 313ms, 内存消耗: 6432K, 提交时间: 2019-11-10 10:38:48

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N=1e5+100;
struct node
{
	ll v;
	int lzy;
	void modify(ll p,int l,int r)
	{
		v=(p+p+r-l)*(r-l+1)/2;
		lzy=p;
	}
}t[N<<2];
#define ls (x<<1)
#define rs (x<<1|1)
void push_down(int x,int l,int r)
{
	if(t[x].lzy)
	{
		int mid=l+r>>1; 
		t[ls].modify(t[x].lzy,l,mid);
		t[rs].modify(mid-l+1+t[x].lzy,mid+1,r);
		t[x].lzy=0;
	}
}
void build(int l,int r,int x)
{
	t[x].lzy=0;
	if(l==r)
	{
		t[x].v=l;
		return ;
	} 
	int mid=l+r>>1;
	build(l,mid,ls);
	build(mid+1,r,rs);
	t[x].v=t[ls].v+t[rs].v;
}
void update(int l,int r,int L,int R,int x)
{
	if(L<=l&&r<=R)
	{
		t[x].modify(l-L+1,l,r);
		return ;
	}
	push_down(x,l,r);
	int mid=l+r>>1;
	if(L<=mid) update(l,mid,L,R,ls);
	if(R>mid) update(mid+1,r,L,R,rs);
	t[x].v=t[ls].v+t[rs].v;
}
ll query(int l,int r,int L,int R,int x)
{
	if(L<=l&&r<=R) return t[x].v;
	push_down(x,l,r);
	int mid=l+r>>1;
	ll ans=0;
	if(L<=mid) ans+=query(l,mid,L,R,ls);
	if(R>mid) ans+=query(mid+1,r,L,R,rs);
	return ans;
}
int main()
{
	int n,m;
	cin>>n>>m;
	build(1,n,1);
	for(int i=1;i<=m;i++)
	{
		int op,l,r;
		cin>>op>>l>>r;
		if(op==1) update(1,n,l,r,1);
		else cout<<query(1,n,l,r,1)<<endl;
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 285ms, 内存消耗: 6620K, 提交时间: 2019-05-11 16:32:52

#include <iostream>
#include <utility>
#include <cstdio>
#include <algorithm>
#include <set>
#include <cstdio>
#include <cmath>
#include <string>
#include <set>
using namespace std;
int main()
{
	long long n,m;
	cin>>n>>m;
	set<pair<long long,long long>> s;
	s.insert({1,1});
	s.insert({n+1,0});
	while(m--)
	{
		long long k,l,r;
		cin>>k>>l>>r;
		if(l>r) continue;
		if(k==1)
		{
			auto it1=s.upper_bound({r,10000000});
			auto it2=it1--;
			pair<long long,long long> p={r+1,it1->second+r+1-it1->first};
			long long o=1;
			if(r==n||r+1==it2->first) o=0;
			it1=s.lower_bound({l,0});
			while(it1!=s.end()&&it1->first<=r) it1=s.erase(it1);
			//for(auto i:s) if(i.first>=l&&i.first<=r) s.erase(i);//improve
			s.insert({l,1});
			if(o) s.insert(p);
		}
		else
		{
			long long ss=0;
			long long i=l;
			while(i!=r+1)
			{
				auto it1=s.lower_bound({i+1,0});
				auto it2=it1--;
				long long rr=min(r+1,it2->first),a0=it1->second+i-it1->first,nn=rr-i,an=a0+nn-1;
				ss+=(a0+an)*nn/2;
				i=rr;
			}
			//for(auto i:s) cout<<i.first<<' '<<i.second<<endl;
			cout<<ss<<endl;
		}
	}
}

上一题