# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1197382 | Godgift42 | 원숭이와 사과 나무 (IZhO12_apple) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000000009;
vector<int> l(8000000,0);
vector<int> r(8000000,0);
vector<int> st(8000000,0);
vector<int> lz(8000000,0);
int nodes=1;
void psh(int v,int tl,int tr,int tm){
if(!lz[v])return;
st[l[v]]=tm-tl+1;
st[r[v]]=tr-tm;
lz[l[v]]=1;
lz[r[v]]=1;
lz[v]=0;
}
void upd(int v, int tl, int tr,int left, int right){
if(tl==left and tr==right){
st[v]=(right-left+1);
lz[v]=1;
return;
}
if(l[v]==0){
nodes++;
l[v]=nodes;
}
if(r[v]==0){
nodes++;
r[v]=nodes;
}
int tm=(tl+tr)/2;
psh(v,tl,tr,tm);
if(tm>=right)upd(l[v],tl,tm,left,right);
else if(left>tm)upd(r[v],tm+1,tr,left,right);
else{
upd(l[v],tl,tm,left,tm);
upd(r[v],tm+1,tr,tm+1,right);
}
st[v] = st[l[v]] + st[r[v]];
}
int sm(int v, int tl, int tr,int left, int right){
if(tl==left and tr==right){
return st[v];
}
if(l[v]==0){
nodes++;
l[v]=nodes;
}
if(r[v]==0){
nodes++;
r[v]=nodes;
}
int tm=(tl+tr)/2;
psh(v,tl,tr,tm);
if(tm>=right)return sm(l[v],tl,tm,left,right);
else if(left>tm)return sm(r[v],tm+1,tr,left,right);
else{
return sm(l[v],tl,tm,left,tm)+sm(r[v],tm+1,tr,tm+1,right);
}
}
int main(){
int m;
cin >> m;
int cur=0;
while(m--){
int k;
cin >> k;
int x,y;
cin >> x >> y;
if(k==1){
cur=sm(1,1,MAXN,x+cur,y+cur);
cout << cur <<"\n";
}
else{
upd(1,1,MAXN,x+cur,y+cur);
}
}
}*/
/*chockolateman
#include<bits/stdc++.h>
using namespace std;
int N,Q,a[200005],st[20000005],l[2000 0005],r[20000005],Nodes = 1;
void update(int pos,int val,int v = 1,int start = 1,int end = 1e9)
{
if(start==end)
{
st[v] += val;
return;
}
if(l[v]==0)
l[v] = ++Nodes;
if(r[v]==0)
r[v] = ++Nodes;
int mid = (start + end)/2;
if(pos <= mid)
update(pos,val,l[v],start,mid);
else
update(pos,val,r[v],mid+1,end);
st[v] = st[l[v]] + st[r[v]];
}
int query(int left,int right,int v = 1,int start = 1,int end = 1e9)
{
if(start==left && end==right)
return st[v];
if(l[v]==0)
l[v] = ++Nodes;
if(r[v]==0)
r[v] = ++Nodes;
int mid = (start + end)/2;
if(right <= mid)
return query(left,right,l[v],start,mid);
else if(left > mid)
return query(left,right,r[v],mid+1,end);
else
return query(left,mid,l[v],start,mid) + query(mid+1,right,r[v],mid+1,end);
}
int main()
{
scanf("%d%d",&N,&Q);
for(int i = 1 ; i <= N ; i++)
{
scanf("%d",&a[i]);
update(a[i],1);
}
for(int x,y,i = 1 ; i <= Q ; i++)
{
char op;
scanf(" %c%d%d",&op,&x,&y);
if(op=='?')
printf("%d\n",query(x,y));
else
{
update(a[x],-1);
a[x] = y;
update(a[x],1);
}
}
return 0;
}*/