[BZOJ] [P3110] [Zjoi 2013] [K 대수 조회] [문제 풀이] [전체 2 점]
2876 단어 bzoj
전체 2 점 너무 신 난다.
선분 트 리 로 바 꾸 면 구간 수정 을 지원 할 수 있 습 니 다.
그때 고 통 스 럽 게 나무 커버 를 쓰 고 T 성상 을 하고 싶 어 요.
Code:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cctype>
using namespace std;
const int maxn=50005;
int n,m;
struct seg{
struct node{
int sum,lazy;
node(){sum=lazy=0;}
}t[maxn<<2];
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define L i<<1
#define R i<<1|1
void rz(int i){
t[i].sum=t[L].sum+t[R].sum;
}
void pushdown(int i,int l,int r){
if(t[i].lazy){
int mid=(l+r)>>1;
t[L].lazy+=t[i].lazy;
t[L].sum+=(mid-l+1)*t[i].lazy;
t[R].lazy+=t[i].lazy;
t[R].sum+=(r-mid)*t[i].lazy;
t[i].lazy=0;
}
}
void Add(int i,int l,int r,int l0,int r0,int d){
if(l0<=l&&r0>=r){
t[i].lazy+=d;
t[i].sum+=(r-l+1)*d;
return;
}int mid=(l+r)>>1;
pushdown(i,l,r);
if(l0<=mid)Add(lson,l0,r0,d);
if(r0>mid)Add(rson,l0,r0,d);rz(i);
}
int Qsum(int i,int l,int r,int l0,int r0){
if(l0<=l&&r0>=r)return t[i].sum;
pushdown(i,l,r);
int mid=(l+r)>>1,ans=0;
if(l0<=mid)ans+=Qsum(lson,l0,r0);
if(r0>mid)ans+=Qsum(rson,l0,r0);
return ans;
}
void Add(int l,int r,int d){
Add(1,1,n,l,r,d);
}
int Qsum(int l,int r){
return Qsum(1,1,n,l,r);
}
#undef lson
#undef rson
#undef L
#undef R
}T,T2;
int getint(){
int res=0,f=1;char c=getchar();
while(!isdigit(c))f=f==-1||c=='-'?-1:1,c=getchar();
while(isdigit(c))res=res*10+c-'0',c=getchar();
return res*f;
}
struct qes{
int x,y,z,ty,ind,cur,delta;
qes(int _x=0,int _y=0,int _z=0,int _ty=0,int _ind=0,int _cur=0,int _delta=0):
x(_x),y(_y),z(_z),ty(_ty),ind(_ind),cur(_cur),delta(_delta){}
}q[maxn];
int anss[maxn],mx,md;
bool part(qes &Q){
if(Q.ty==2){
if(Q.cur+Q.delta>Q.z-1)return 1;
Q.cur+=Q.delta;Q.delta=0;return 0;
}return Q.z<=md;
}
void solve(int lef,int rig,int l,int r){
if(lef>rig)return;
if(l==r){
for(int i=lef;i<=rig;i++)if(q[i].ty==2)
anss[q[i].ind]=l;
return;
}int mid=(l+r)>>1;md=mid;
for(int i=lef;i<=rig;i++){
if(q[i].ty==1&&q[i].z<=mid)T.Add(q[i].x,q[i].y,1);
if(q[i].ty==2)q[i].delta=T.Qsum(q[i].x,q[i].y);
}for(int i=lef;i<=rig;i++)
if(q[i].ty==1&&q[i].z<=mid)T.Add(q[i].x,q[i].y,-1);
int dv=stable_partition(q+lef,q+rig+1,part)-q-1;
solve(lef,dv,l,mid);
solve(dv+1,rig,mid+1,r);
}
int main(){
n=getint();m=getint();
for(int i=1;i<=m;i++){
int op=getint(),l=getint(),r=getint(),c=getint();
if(op==1)
q[i]=qes(l,r,c,op),mx=max(mx,c),T2.Add(l,r,1);
else q[i]=qes(l,r,T2.Qsum(l,r)-c+1,op,++anss[0]);
}
solve(1,m,0,mx);
for(int i=1;i<=anss[0];i++)printf("%d
",anss[i]);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
bzoj1010 장난감 포장 [결정 단조성 최적화 dp]하나의 모범 문제라고 할 수 있다.우리는 먼저 소박한 dp방정식을 얻을 수 있다. f[i]=min(f[j]+w(j,i)),j∈[0,i). w(j,i)는 j+1~i를 포장하여 운송하는 비용의 시간 복잡도는 O(n2)라...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.