NC25548. 温暖的签到题
描述
输入描述
第一行包含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; } } }