Link
A - 一棵简单的线段树
标准线段树
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e6+7;
int n,q;
struct node
{
int l,r,maxx,minx;
ll num;
ll sum;
}t[maxn*4];
void build(int x,int l,int r)
{
t[x].l=l,t[x].r=r;
if(l==r)
{
t[x].num=t[x].maxx=t[x].minx=t[x].sum=0;
return;
}
int mid=(l+r)/2;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
t[x].maxx=max(t[x<<1].maxx,t[x<<1|1].maxx);
t[x].minx=min(t[x<<1].minx,t[x<<1|1].minx);
}
void update(int x,int p,int val)
{
int l=t[x].l,r=t[x].r;
if(l==r && l==p){
t[x].num=t[x].sum=t[x].minx=t[x].maxx=val;
return;
}
int mid=(l+r)/2;
if(p<=mid) update(x<<1,p,val);
else update(x<<1|1,p,val);
t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
t[x].maxx=max(t[x<<1].maxx,t[x<<1|1].maxx);
t[x].minx=min(t[x<<1].minx,t[x<<1|1].minx);
}
ll query(int x,int ql,int qr)
{
int l=t[x].l,r=t[x].r;
if(ql<=l && qr>=r)
{
return t[x].sum;
}
int mid=(l+r)/2;
ll ans=0;
if(qr>mid) ans+=query(x<<1|1,ql,qr);
if(ql<=mid) ans+=query(x<<1,ql,qr);
return ans;
}
int querymax(int x,int ql,int qr)
{
int l=t[x].l,r=t[x].r;
if(ql<=l && qr>=r)
{
return t[x].maxx;
}
int mid=(l+r)/2;
int ans=-1e9-2;
if(qr>mid) ans=max(ans,querymax(x<<1|1,ql,qr));
if(ql<=mid) ans=max(ans,querymax(x<<1,ql,qr));
return ans;
}
int querymin(int x,int ql,int qr)
{
int l=t[x].l,r=t[x].r;
if(ql<=l && qr>=r)
{
return t[x].minx;
}
int mid=(l+r)/2;
int ans=1e9+2;
if(qr>mid) ans=min(ans,querymin(x<<1|1,ql,qr));
if(ql<=mid) ans=min(ans,querymin(x<<1,ql,qr));
return ans;
}
int main()
{
while(scanf("%d%d",&n,&q)!=EOF)
{
build(1,1,n);
while(q--)
{
int type,l,r,p,x;
scanf("%d",&type);
if(type==0)
{
scanf("%d%d",&p,&x);
update(1,p,x);
}
else
{
scanf("%d%d",&l,&r);
ll ans=query(1,l,r);
ll maxx=querymax(1,l,r);
ll minx=querymin(1,l,r);
//cout<<ans<<' '<<maxx<<' '<<minx<<endl;
printf("%lld
", ans-maxx-minx);
}
}
}
return 0;
}
B - 一棵普通的线段树
线段树+Lazy标记
记得要将Lazy push_up和push_down
题意
设 xem 表示集合中最小的未出现的正整数， 如 xem{}=1，xem{1,3,4}=2.
定义 bi=xem{bi−ci,bi−ci+1,...,bi−1},i=1,2,...,n 特别的，b0=1b. 给定 n 和 c1,c2,...,cn，请你计算出 b1,b2,...,bn. (n<=1e6)
第一行一个n，第二行c1，c2.........cn （1<=ci<=i）
输出n个数依次为b1，b2，b3......bn
分析
D - 一棵复杂的线段树
题意
给出了一个数组 A[1..n]， 初始元素为 a1,a2,...,an 是 1∼n 的一个排列. 然后对数组施以了 m 个操作. 每个操作针对一个区间 [l,r] (1≤l≤r≤n)，将区间内的元素从小到大排序或者从大到小排序.
给出n，k，m，有m条操作，给出三个数o，l，r，o=0，代表区间[l,r]从小到大排序，o=1，从大到小，输出最终的第k个数即A[k] ( n(1≤n≤105) 和 k(1≤k≤n) )
分析
由于数为1~n且我们只求第k个元素，故只关注第k个元素
二分答案即最后第k个数，首先将所有大于mid的设为1，小与等于的为0，每次对区间排序操作相当于改变区间内的0和1的顺序，比如：设区间[l,r]中1的数量为c，① 对区间[l,r]进行升序操作，相当于将区间[l,r]全部设为0后，将最后c个设为1,即[L,R-c+1]， ② 对区间[l,r]进行升序操作时，反之 。所有操作后，由于我们一开始将答案所在的数设为0，最后一个是的[k,k]区间为0的即为答案
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5+7;
int a[maxn];
int type[maxn],ql[maxn],qr[maxn];
struct node
{
int l,r,sum;
int lazy;
}t[maxn*4];
void build(int x,int l,int r,int mid)
{
t[x].l=l,t[x].r=r;
t[x].lazy=-1;
if(l==r){
if(a[l]>mid)
t[x].sum=1;
else
t[x].sum=0;
return;
}
int m=(l+r)/2;
build(x<<1,l,m,mid);
build(x<<1|1,m+1,r,mid);
t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}
void update(int x,int ql,int qr,int val){
int l=t[x].l, r=t[x].r;
if(ql<=l && qr>=r){
t[x].sum=(r-l+1)*val;
t[x].lazy=val;
return;
}
if(t[x].lazy!=-1){
t[x<<1].lazy=t[x].lazy;
t[x<<1|1].lazy=t[x].lazy;
t[x<<1].sum=(t[x<<1].r-t[x<<1].l+1)*t[x].lazy;
t[x<<1|1].sum=(t[x<<1|1].r-t[x<<1|1].l+1)*t[x].lazy;
t[x].lazy=-1;
}
int mid=(l+r)/2;
if(qr>mid) update(x<<1|1,ql,qr,val);
if(ql<=mid) update(x<<1,ql,qr,val);
t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}
int query(int x,int ql,int qr)
{
int l=t[x].l,r=t[x].r;
if(ql<=l && qr>=r){
return t[x].sum;
}
if(t[x].lazy!=-1){
t[x<<1].lazy=t[x].lazy;
t[x<<1|1].lazy=t[x].lazy;
t[x<<1].sum=(t[x<<1].r-t[x<<1].l+1)*t[x].lazy;
t[x<<1|1].sum=(t[x<<1|1].r-t[x<<1|1].l+1)*t[x].lazy;
t[x].lazy=-1;
}
int mid=(l+r)/2;
int ans=0;
if(qr>mid) ans+=query(x<<1|1,ql,qr);
if(ql<=mid) ans+=query(x<<1,ql,qr);
t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
return ans;
}
int main()
{
int n,k,m;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d", &type[i], &ql[i], &qr[i]);
}
int l=1,r=n;
while(l<r){
int mid=(l+r)/2;
build(1,1,n,mid);
for(int i=1;i<=m;i++){
int num=query(1,ql[i],qr[i]);
update(1,ql[i],qr[i],0);
if(type[i]){
update(1,ql[i],ql[i]+num-1,1);
}
else{
update(1,qr[i]-num+1,qr[i],1);
}
}
if(query(1,k,k)){
l=mid+1;
}
else
r=mid;
}
printf("%d
",l);
return 0;
}
E - 小埋的steam愿望单
题意
小埋有一个steam愿望单，上面记载着她想买的游戏！现在小埋有以下 n 个操作：
1 x y 添加一个价格为 y 名字为 x 的游戏加入愿望单
2 x 删除名字为 x 的游戏
3 x y 名字为 x 的游戏价格调整为 y
4 x 为 1 输出最便宜的游戏的名字(如果有多个同价格游戏输出字典序最小的)，x 为 2 输出最贵的游戏(如果有多个同价格游戏输出字典序最大的) ( n<=1e5 )
不合法的情况请忽略该操作
分析
STL Set，set支持begin、end、erase等操作，用set按题意模拟即可，对于可能的无效操作，map哈希判断一下存在不存在即可
F - 好吃不饺子
题意
饺子发现身边危机四伏！有n个人站在一维平面上，每个人的坐标为Ai，能量值为Bi。饺子有c种方法可以推测出有多少人想吃饺子，请你求出每种方法可以得出的想吃饺子的人数
第一行两个值 n（n≤105), c(c≤10)
接下来n行每行两个值Ai,Bi(1≤Ai≤109,1≤Bi≤104,Ai≤Aj Ai,Bi i<j)
接下来c行，每行包含三个数K,function,length
其中
K可能为gt或者lt，代表大于或者小于
function可能为min，max或者avg，代表最小，最大或者平均
lengthl是一个整数(1≤length≤1e9)
K,function,length的意思为对于第i号人，如果Bi K于[Ai−length,Ai)范围内的所有人能量值的function值，说明该人想吃饺子，特别的如果范围内一个人也没有，则这个人不想吃饺子
分析
由于Ai的数据范围，刚开始我考虑以Ai值为叶子节点动态建树，然后查询即可，实现起来有点麻烦，原因：找错了建树的区间
一直wa2，还没改过去
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+7;
int n,c,A[maxn],B[maxn],cnt;
struct node{
int l,r,lson,rson,b,maxx,minx,sum,num;
}t[maxn*40];
int root;
int newnode()
{
++cnt;
return cnt;
}
void build(int &x,int l ,int r,int p,int val){
if(!x) x=newnode();
t[x].l=l,t[x].r=r;
t[x].num++;
if(l==r)
{
t[x].sum+=val;
t[x].maxx=max(t[x].maxx,val);
if(!t[x].minx) t[x].minx=val;
else t[x].minx=min(t[x].minx,val);
return;
}
int mid=(l+r)/2;
if(p<=mid) build(t[x].lson,l,mid,p,val);
else build(t[x].rson,mid+1,r,p,val);
t[x].sum=t[t[x].lson].sum+t[t[x].rson].sum;
t[x].maxx=max(t[t[x].lson].maxx,t[t[x].rson].maxx);
if(!t[t[x].lson].minx)t[x].minx=t[t[x].rson].minx;
else if(!t[t[x].rson].minx) t[x].minx=t[t[x].lson].minx;
else t[x].minx=min(t[t[x].lson].minx,t[t[x].rson].minx);
return;
}
int querymax(int x,int ql,int qr)
{
int l=t[x].l,r=t[x].r;
if(ql<=l && qr>=r)
return t[x].maxx;
int mid=(l+r)/2;
int ans=0;
if(qr>mid)
{
if(t[x].rson) ans=max(ans,querymax(t[x].rson,ql,qr));
}
if(ql<=mid)
{
if(t[x].lson) ans=max(ans,querymax(t[x].lson,ql,qr));
}
return ans;
}
int querymin(int x,int ql,int qr)
{
int l=t[x].l,r=t[x].r;
if(ql<=l && qr>=r)
return t[x].minx;
int mid=(l+r)/2;
int ans=1e9+5;
if(qr>mid)
{
if(t[x].rson) ans=min(ans,querymin(t[x].rson,ql,qr));
}
if(ql<=mid)
{
if(t[x].lson) ans=min(ans,querymin(t[x].lson,ql,qr));
}
return ans;
}
ll querysum(int x,int ql,int qr)
{
int l=t[x].l,r=t[x].r;
if(ql<=l && qr>=r)
return t[x].sum;
int mid=(l+r)/2;
ll ans=0;
if(qr>mid)
{
if(t[x].rson)ans+=1LL*querysum(t[x].rson,ql,qr);
}
if(ql<=mid)
{
if(t[x].lson)ans+=1LL*querysum(t[x].lson,ql,qr);
}
return ans;
}
int querynum(int x,int ql,int qr)
{
int l=t[x].l,r=t[x].r;
if(ql<=l && qr>=r)
return t[x].num;
int mid=(l+r)/2;
ll ans=0;
if(qr>mid)
{
if(t[x].rson)ans+=1LL*querynum(t[x].rson,ql,qr);
}
if(ql<=mid) {
if(t[x].lson)ans+=1LL*querynum(t[x].lson,ql,qr);
}
return ans;
}
int main()
{
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++) scanf("%d%d",&A[i],&B[i]),build(root,1,1e9,A[i],B[i]);
while(c--)
{
char k[10],f[10];
int len;
scanf("%s%s%d",&k,&f,&len);
ll cnt=0;
if(k[0]=='g')
{
if(f[2]=='n')
{
for(int i=2;i<=n;i++)
{
int lz=max(1,A[i]-len);
if(lz >= A[i]) continue;
ll kk=querymin(root,lz,A[i]-1);
if(B[i]>kk && kk && kk!=(1e9 + 5))
cnt++;
}
}
else if(f[2]=='x')
{
for(int i=2;i<=n;i++)
{
int lz=max(1,A[i]-len);
if(lz >= A[i]) continue;
ll kk=querymax(root,lz,A[i]-1);
if(B[i]>kk&&kk)
cnt++;
}
}
else
{
for(int i=2;i<=n;i++)
{
int lz=max(1,A[i]-len);
if(lz >= A[i]) continue;
double kk=(1.0*querysum(root,lz,A[i]-1))/(querynum(root,lz,A[i]-1));
if(B[i]>kk && kk)
cnt++;
}
}
}
else
{
if(f[2]=='n')
{
for(int i=2;i<=n;i++)
{
int lz=max(1,A[i]-len);
if(lz >= A[i]) continue;
ll kk=querymin(root,lz,A[i]-1);
if(B[i]<kk && kk && kk!=(1e9 + 5))
cnt++;
}
}
else if(f[2]=='x')
{
for(int i=2;i<=n;i++)
{
int lz=max(1,A[i]-len);
if(lz >= A[i]) continue;
ll kk=querymax(root,lz,A[i]-1);
if(B[i]<kk && kk)
cnt++;
}
}
else
{
for(int i=2;i<=n;i++)
{
int lz=max(1,A[i]-len);
if(lz <= A[i]) continue;
double kk=(1.0*querysum(root,lz,A[i]-1))/(querynum(root,lz,A[i]-1));
if(B[i]<kk && kk)
cnt++;
}
}
}
printf("%lld
",cnt);
}
return 0;
}
实际上无需动态建树，由于Ai是非递减的，考虑以Bi为叶子节点建树，1~n每个节点代表Bi即可，对于每个询问二分得到查询区间的左边界，线段树查询即可
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define ll long long
using namespace std;
const int MaxN=100010;
const double INF=1e9;
struct part{
double maxx;
double min;
double sum;
};
ll n,c,ans,i,j;
double a[100010],b[100010],length,v;
char func[100],k[100];
struct part s[MaxN*4];
void pushup(ll rt)
{
s[rt].sum=s[rt*2].sum+s[rt*2+1].sum;
s[rt].max=max(s[rt*2].max,s[rt*2+1].max);
s[rt].min=min(s[rt*2].min,s[rt*2+1].min);
}
void build(ll rt,ll l,ll r)
{
if (l==r)
{
s[rt].sum=s[rt].max=s[rt].min=b[l];
return;
}
ll mid=(l+r)/2;
build(rt*2,l,mid);
build(rt*2+1,mid+1,r);
pushup(rt);
}
double findsum(ll rt,ll l,ll r,ll L,ll R)
{
double ans;
if (L<=l&&r<=R)
{
return(s[rt].sum);
}
ll mid=(l+r)/2;
ans=0;
if (L<=mid) ans+=findsum(rt*2,l,mid,L,R);
if (R>mid) ans+=findsum(rt*2+1,mid+1,r,L,R);
return(ans);
}
double findmax(ll rt,ll l,ll r,ll L,ll R)
{
double ans;
if (L<=l&&r<=R)
{
return(s[rt].max);
}
ll mid=(l+r)/2;
ans=-INF;
if (L<=mid) ans=max(ans,findmax(rt*2,l,mid,L,R));
if (R>mid) ans=max(ans,findmax(rt*2+1,mid+1,r,L,R));
return(ans);
}
double findmin(ll rt,ll l,ll r,ll L,ll R)
{
double ans;
if (L<=l&&r<=R)
{
return(s[rt].min);
}
ll mid=(l+r)/2;
ans=INF;
if (L<=mid) ans=min(ans,findmin(rt*2,l,mid,L,R));
if (R>mid) ans=min(ans,findmin(rt*2+1,mid+1,r,L,R));
return(ans);
}
int main()
{
scanf("%lld%lld",&n,&c);
for (i=1;i<=n;i++)
scanf("%lf%lf",&a[i],&b[i]);
build(1,1,n);
for (i=1;i<=c;i++)
{
cin>>k>>func>>length;
ans=0;
for (j=1;j<=n;j++)
{
ll l=lower_bound(a+1,a+n+1,a[j]-length)-a;
ll r=j;
while (r>0&&a[r]==a[r-1]) r--;
r--;
if (l<=r)
{
if (strcmp(func,"avg")==0) v=findsum(1,1,n,l,r)/(r-l+1); else
if (strcmp(func,"max")==0) v=findmax(1,1,n,l,r); else
if (strcmp(func,"min")==0) v=findmin(1,1,n,l,r);
if ((b[j]>v&&strcmp(k,"gt")==0)||(b[j]<v&&strcmp(k,"lt")==0)) ans++;
}
}
printf("%lld
",ans);
}
return(0);
}
G - 三澄美琴的心里只有学习
题意
分析
H - 中堂系的困难任务
题意
分析
I - 不如把并查集加上个计数功能吧
题意
分析
J - 老头马桶枪！
题意
分析
K - 爱吃瓜的伊卡洛斯(1)
题意
分析
L - 爱吃瓜的伊卡洛斯(2)
题意
分析
M - 一道普通题1
题意
分析
N - 一道普通的题2
题意
分析
O - 帆宝RMQ
题意
分析
P - 为什么你这么熟练啊
题意
分析
Q - 这是一道简单题
题意
分析
Summary: