安利一波 黄学长pdf对应的loj练习 分块入门题https://loj.ac/problems?page=13
贴下弱鸡如我的代码....表示分块入门风格学的黄学长的23333
分块练习一
#include <bits/stdc++.h>
#define N 50005
#define ll long long
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
int size,t,n;
ll a[N];
ll flag[505];
int p[N];
void add(int l,int r,int c){
for(int i=l;i<=min(p[l]*size,r);i++) a[i]+=c;
if(p[l]!=p[r]){
for(int i=(p[r]-1)*size+1;i<=r;i++) a[i]+=c;
}
for(int i=p[l]+1;i<=p[r]-1;i++) flag[i]+=c;
}
int main(){
// ios::sync_with_stdio(false);
// freopen("data.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
size=(int)sqrt(n);
for(int i=1;i<=n;i++) p[i]=(i-1)/size+1;
int op,l,r,c;
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&op,&l,&r,&c);
if(op==0){
add(l,r,c);
}
else{
printf("%lld
",a[r]+flag[p[r]]);
}
}
return 0;
}
分块练习二
#include <bits/stdc++.h>
#define N 50005
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
int a[N],b[N];
int size,n;
int p[N],lr[505],rr[505],flag[505];
void add(int l,int r,int c){
for(int i=l;i<=min(r,p[l]*size);i++) a[i]+=c;
for(int i=lr[p[l]];i<=rr[p[l]];i++) b[i]=a[i];
sort(b+lr[p[l]],b+rr[p[l]]+1);
if(p[l]!=p[r]){
for(int i=lr[p[r]];i<=r;i++) a[i]+=c;
for(int i=lr[p[r]];i<=rr[p[r]];i++) b[i]=a[i];
sort(b+lr[p[r]],b+rr[p[r]]+1);
}
for(int i=p[l]+1;i<=p[r]-1;i++) flag[i]+=c;
}
int querty(int l,int r,int c){
int ans=0;
for(int i=l;i<=min(r,p[l]*size);i++){
if(a[i]+flag[p[l]]<c) ans++;
}
if(p[l]!=p[r]){
for(int i=lr[p[r]];i<=r;i++){
if(a[i]+flag[p[r]]<c) ans++;
}
}
for(int i=p[l]+1;i<=p[r]-1;i++){
int l1=lr[i];int r1=rr[i];int t=c-flag[i]-1;
int ans1=0;
while(l1<=r1){
int mid=(l1+r1)>>1;
if(b[mid]<=t){
ans1=mid;l1=mid+1;
}
else r1=mid-1;
}
if(ans1!=0) ans+=(ans1-lr[i]+1);
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
scanf("%d",&n);size=(int)sqrt(n)/2;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);b[i]=a[i];
p[i]=(i-1)/size+1;
}
lr[1]=1;
for(int i=2;i<n;i++){
if(p[i]!=p[i+1]){
rr[p[i]]=i;lr[p[i+1]]=i+1;
}
}
rr[p[n]]=n;
for(int i=1;i<=p[n];i++){
sort(b+lr[i],b+rr[i]+1);
}
int op,l,r,c;
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&op,&l,&r,&c);
if(op==0) add(l,r,c);
else printf("%d
",querty(l,r,c*c));
}
return 0;
}
分块入门练习三
#include <bits/stdc++.h>
#define N 100005
#define ll long long
#define INF 10000000007
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
ll a[N],b[N];
int size,n;
int p[N],lr[1005],rr[1005];
ll flag[1005];
void add(int l,int r,ll c){
for(int i=l;i<=min(r,p[l]*size);i++) a[i]+=c;
for(int i=lr[p[l]];i<=rr[p[l]];i++) b[i]=a[i];
sort(b+lr[p[l]],b+rr[p[l]]+1);
if(p[l]!=p[r]){
for(int i=lr[p[r]];i<=r;i++) a[i]+=c;
for(int i=lr[p[r]];i<=rr[p[r]];i++) b[i]=a[i];
sort(b+lr[p[r]],b+rr[p[r]]+1);
}
for(int i=p[l]+1;i<=p[r]-1;i++) flag[i]+=c;
}
ll querty(int l,int r,ll c){
ll ans=-1;
for(int i=l;i<=min(r,p[l]*size);i++){
if(a[i]+flag[p[l]]<c) ans=max(ans,a[i]+flag[p[l]]);
}
if(p[l]!=p[r]){
//cout<<lr[p[r]]<<" "<<r<<endl;
for(int i=lr[p[r]];i<=r;i++){
if(a[i]+flag[p[r]]<c) ans=max(ans,a[i]+flag[p[r]]);
}
}
for(int i=p[l]+1;i<=p[r]-1;i++){
int l1=lr[i];int r1=rr[i];int t=c-flag[i]-1;
int ans1=0;
while(l1<=r1){
int mid=(l1+r1)>>1;
if(b[mid]<=t){
ans1=mid;l1=mid+1;
}
else r1=mid-1;
}
if(ans1!=0) ans=max(ans,b[ans1]+flag[i]);
}
//if(ans==-1*INF) return -1;
return ans;
}
int main(){
ios::sync_with_stdio(false);
scanf("%d",&n);size=(int)sqrt(n)*3;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);b[i]=a[i];
p[i]=(i-1)/size+1;
}
lr[1]=1;
for(int i=1;i<n;i++){
if(p[i]!=p[i+1]){
rr[p[i]]=i;lr[p[i+1]]=i+1;
}
}
rr[p[n]]=n;
for(int i=1;i<=p[n];i++){
sort(b+lr[i],b+rr[i]+1);
}
int op,l,r;ll c;
for(int i=1;i<=n;i++){
scanf("%d%d%d%lld",&op,&l,&r,&c);
if(op==0) add(l,r,c);
else printf("%lld
",querty(l,r,c));
}
return 0;
}
分块入门练习四
#include <bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
ll a[N],flag[N],sum[N];
int n,size;
int p[N];
void add(int l,int r,ll c){
for(int i=l;i<=min(r,p[l]*size);i++) a[i]+=c,sum[p[l]]+=c;
if(p[l]!=p[r]){
for(int i=(p[r]-1)*size+1;i<=r;i++) a[i]+=c,sum[p[r]]+=c;
}
for(int i=p[l]+1;i<=p[r]-1;i++) flag[i]+=c;
}
ll Sum(int l,int r,ll c){
ll ans=0;
for(int i=l;i<=min(r,p[l]*size);i++) ans=(ans+a[i]+flag[p[l]]);
if(p[l]!=p[r]){
for(int i=size*(p[r]-1)+1;i<=r;i++) ans=(ans+a[i]+flag[p[r]]);
}
for(int i=p[l]+1;i<=p[r]-1;i++) ans=(ans+sum[i]+flag[i]*size);
return ans;
}
int main(){
ios::sync_with_stdio(false);
scanf("%d",&n);size=(int)sqrt(n)/2;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++){
p[i]=(i-1)/size+1;
sum[p[i]]+=a[i];
}
int op,l,r;ll c;
for(int i=1;i<=n;i++){
scanf("%d%d%d%lld",&op,&l,&r,&c);
if(op==0) add(l,r,c);
else printf("%lld
",Sum(l,r,c)%(c+1));
}
return 0;
}
分块入门练习五
#include <bits/stdc++.h>
#define N 100005
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
int p[N],n,size;
int a[N],mx[N],sum[N];
void sqr(int l,int r){
//if(mx[p[l]]>1){
for(int i=l;i<=min(r,p[l]*size);i++){
sum[p[l]]-=a[i];a[i]=sqrt(a[i]);sum[p[l]]+=a[i];
}
//mx[p[l]]=-1;
//for(int i=(p[l]-1)*size+1;i<=min(p[l]*size,n);i++) mx[p[l]]=max(mx[p[l]],a[i]);
// }
if(p[r]!=p[l]){
// if(mx[p[r]]>1){
for(int i=(p[r]-1)*size+1;i<=r;i++){
sum[p[r]]-=a[i];a[i]=sqrt(a[i]);sum[p[r]]+=a[i];
}
//mx[p[r]]=-1;
//for(int i=(p[r]-1)*size+1;i<=min(p[r]*size,n);i++) mx[p[r]]=max(mx[p[r]],a[i]);
// }
}
for(int i=p[l]+1;i<=p[r]-1;i++){
if(mx[i]<=1) continue;
sum[i]=0;mx[i]=-1;
for(int j=(i-1)*size+1;j<=i*size;j++){
a[j]=sqrt(a[j]);sum[i]+=a[j];mx[i]=max(mx[i],a[j]);
}
}
}
int Sum(int l,int r){
int ans=0;
for(int i=l;i<=min(r,p[l]*size);i++) ans+=a[i];
if(p[l]!=p[r]){
for(int i=(p[r]-1)*size+1;i<=r;i++) ans+=a[i];
}
for(int i=p[l]+1;i<=p[r]-1;i++) ans+=sum[i];
return ans;
}
int main(){
ios::sync_with_stdio(false);
scanf("%d",&n);size=(int)sqrt(n)/2;
for(int i=1;i<=n;i++) mx[i]=-1;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
p[i]=(i-1)/size+1;mx[p[i]]=max(mx[p[i]],a[i]);
sum[p[i]]+=a[i];
}
int op,l,r,c;
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&op,&l,&r,&c);
if(op==0) sqr(l,r);
else printf("%d
",Sum(l,r));
}
return 0;
}
分块入门练习六
#include <bits/stdc++.h>
#define N 100005
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
vector<int>vec[1005];
int n,size,t;int a[N];int b[N<<1];
void chong(){
int u=0;
for(int i=1;i<=t;i++){
for(int j=0;j<vec[i].size();j++) b[++u]=vec[i][j];
}
for(int i=1;i<=t;i++) vec[i].clear();
size=(int)sqrt(u);
for(int i=1;i<=u;i++) vec[(i-1)/size+1].push_back(b[i]);
t=(u-1)/size+1;
}
void insert(int pos,int vul){
int p=0;int pos1;
for(int i=1;i<=t;i++){
if(p+vec[i].size()>=pos){
pos1=i;break;
}
p+=vec[i].size();
}
pos-=p;
vec[pos1].insert(vec[pos1].begin()+pos-1,vul);
if(vec[pos1].size()>20*size) chong();
}
int querty(int pos){
int p=0;
for(int i=1;i<=t;i++){
if(p+vec[i].size()>=pos){
return vec[i][pos-p-1];
}
p+=vec[i].size();
}
}
int main(){
ios::sync_with_stdio(false);
scanf("%d",&n);size=(int)sqrt(n)/2;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
vec[(i-1)/size+1].push_back(a[i]);
}
t=(n-1)/size+1;
int op,l,r,c;
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&op,&l,&r,&c);
if(op==0) insert(l,r);
else printf("%d
",querty(r));
}
return 0;
}
分块入门练习七
#include <bits/stdc++.h>
#define N 100005
#define lth 10007
#define ll long long
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
ll a[N];int p[N];
ll flag1[N],flag2[N];
int n,size;
void add(int l,int r,ll c){
for(int i=size*(p[l]-1)+1;i<=min(n,size*p[l]);i++) a[i]=(a[i]*flag1[p[l]]%lth+flag2[p[l]])%lth;
flag1[p[l]]=1;flag2[p[l]]=0;
for(int i=l;i<=min(r,size*p[l]);i++) a[i]=(a[i]+c)%lth;
if(p[l]!=p[r]){
for(int i=size*(p[r]-1)+1;i<=min(n,size*p[r]);i++) a[i]=(a[i]*flag1[p[r]]%lth+flag2[p[r]])%lth;
flag1[p[r]]=1;flag2[p[r]]=0;
for(int i=(p[r]-1)*size+1;i<=r;i++) a[i]=(a[i]+c)%lth;
}
for(int i=p[l]+1;i<=p[r]-1;i++) flag2[i]=(flag2[i]+c)%lth;
}
void cheng(int l,int r,ll c){
for(int i=size*(p[l]-1)+1;i<=min(n,size*p[l]);i++) a[i]=(a[i]*flag1[p[l]]%lth+flag2[p[l]])%lth;
flag1[p[l]]=1;flag2[p[l]]=0;
for(int i=l;i<=min(r,p[l]*size);i++){
a[i]=(a[i]*c)%lth;
}
if(p[l]!=p[r]){
for(int i=size*(p[r]-1)+1;i<=min(n,size*p[r]);i++) a[i]=(a[i]*flag1[p[r]]%lth+flag2[p[r]])%lth;
flag1[p[r]]=1;flag2[p[r]]=0;
for(int i=(p[r]-1)*size+1;i<=r;i++){
a[i]=(a[i]*c)%lth;
}
}
for(int i=p[l]+1;i<=p[r]-1;i++){
flag1[i]=(c*flag1[i])%lth;flag2[i]=(c*flag2[i])%lth;
}
}
int main(){
ios::sync_with_stdio(false);
scanf("%d",&n);size=(int)sqrt(n)/2;
for(int i=1;i<=n;i++) flag1[i]=1;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
p[i]=(i-1)/size+1;
}
int op,l,r,c;
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&op,&l,&r,&c);
if(op==0) add(l,r,c);
else if(op==1) cheng(l,r,c);
else printf("%lld
",(a[r]*flag1[p[r]]%lth+flag2[p[r]])%lth);
}
return 0;
}
分块入门练习八
#include <bits/stdc++.h>
#define N 100005
#define INF 10000000007
#define ll long long
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
ll a[N],flag[N];
int p[N];
int n,size;
void push(int x){
if(flag[x]==INF) return ;
for(int i=(x-1)*size+1;i<=min(n,x*size);i++){
a[i]=flag[x];
}
flag[x]=INF;
}
int querty(int l,int r,int c){
push(p[l]);
int ans=0;
for(int i=l;i<=min(r,p[l]*size);i++){
if(a[i]==c) ans++;
else a[i]=c;
}
if(p[l]!=p[r]){
push(p[r]);
for(int i=(p[r]-1)*size+1;i<=r;i++){
if(a[i]==c) ans++;
else a[i]=c;
}
}
for(int i=p[l]+1;i<=p[r]-1;i++){
if(flag[i]==INF){
flag[i]=c;
for(int j=(i-1)*size+1;j<=i*size;j++){
if(a[j]==c) ans++;
}
}
else if(flag[i]==c) ans+=size;
else flag[i]=c;
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
scanf("%d",&n);size=(int)sqrt(n)/2;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
p[i]=(i-1)/size+1;flag[i]=INF;
}
int l,r,c;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&l,&r,&c);
printf("%d
",querty(l,r,c));
}
return 0;
}
分块入门练习九 //求区间众数经典题
#include <bits/stdc++.h>
#define N 100005
#define pii pair<int,int>
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
int n,size;
int sum[805][N],num[805][805],cc[805][805];//num 次数 cc 数字
int a[N],p[N];
int tmp[N];
vector<int>vec;
int querty(int l,int r){
//cout<<p[l]<<" "<<p[r]<<endl;
if(p[r]-p[l]<=1){
int pos,nu=0;
for(int i=l;i<=r;i++) tmp[a[i]]=0;
for(int i=l;i<=r;i++){
tmp[a[i]]++;
if(tmp[a[i]]>=nu){
if(tmp[a[i]]==nu) pos=min(pos,a[i]);
else pos=a[i];
nu=tmp[a[i]];
}
}
return pos;
}
int pos=cc[p[l]+1][p[r]-1];int nu=num[p[l]+1][p[r]-1];
// cout<<pos<<" "<<nu<<" "<<p[l]+1<<" "<<p[r]-1<<endl;
for(int i=l;i<=p[l]*size;i++) tmp[a[i]]=sum[p[r]-1][a[i]]-sum[p[l]][a[i]];
for(int i=(p[r]-1)*size+1;i<=r;i++) tmp[a[i]]=sum[p[r]-1][a[i]]-sum[p[l]][a[i]];
for(int i=l;i<=p[l]*size;i++){
tmp[a[i]]++;
if(tmp[a[i]]>=nu){
if(tmp[a[i]]==nu) pos=min(pos,a[i]);
else pos=a[i];
nu=tmp[a[i]];
}
}
for(int i=(p[r]-1)*size+1;i<=r;i++){
tmp[a[i]]++;
if(tmp[a[i]]>=nu){
if(tmp[a[i]]==nu) pos=min(a[i],pos);
else pos=a[i];
nu=tmp[a[i]];
}
}
return pos;
}
int main(){
ios::sync_with_stdio(false);
scanf("%d",&n);size=(int)sqrt(n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);vec.push_back(a[i]);
p[i]=(i-1)/size+1;
}
sort(vec.begin(),vec.end());
int t=unique(vec.begin(),vec.end())-vec.begin();
for(int i=1;i<=n;i++) a[i]=lower_bound(vec.begin(),vec.begin()+t,a[i])-vec.begin()+1;
for(int i=1;i<=p[n];i++){
for(int j=1;j<=t;j++) sum[i][j]=sum[i-1][j];
for(int j=(i-1)*size+1;j<=min(n,size*i);j++) sum[i][a[j]]++;
}
for(int i=1;i<=p[n];i++){
num[i][i]=0;
for(int j=(i-1)*size+1;j<=min(n,i*size);j++){
if(sum[i][a[j]]-sum[i-1][a[j]]>=num[i][i]){
if(sum[i][a[j]]-sum[i-1][a[j]]==num[i][i]) cc[i][i]=min(a[j],cc[i][i]);
else cc[i][i]=a[j];
num[i][i]=sum[i][a[j]]-sum[i-1][a[j]];
}
}
for(int j=i+1;j<=p[n];j++){
num[i][j]=num[i][j-1];cc[i][j]=cc[i][j-1];
for(int k=(j-1)*size+1;k<=min(n,j*size);k++){
if(sum[j][a[k]]-sum[i-1][a[k]]>=num[i][j]){
if(sum[j][a[k]]-sum[i-1][a[k]]==num[i][j]) cc[i][j]=min(cc[i][j],a[k]);
else cc[i][j]=a[k];
num[i][j]=sum[j][a[k]]-sum[i-1][a[k]];
}
}
// cout<<i<<" "<<j<<" "<<num[i][j]<<"==========="<<cc[i][j]<<endl;
}
}
int l,r;
for(int i=1;i<=n;i++){
scanf("%d%d",&l,&r);
if(l>r) swap(l,r);
// cout<<querty(l,r)<<endl;
///cout<<num[31][31]<<" "<<cc[31][31]<<endl;
printf("%d
",vec[querty(l,r)-1]);
}
return 0;
}
结尾彩蛋// splay没把分块跑过....常数有点大大噢
#include <bits/stdc++.h>
#define N 200005
#define rl ch[ch[root][1]][0]
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
int ch[N][2],key[N],size[N],pre[N];
int cnt,root,a[N],n;
void Treavel(int x)
{
if(x)
{
// cout<<x<<endl;
Treavel(ch[x][0]);
printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size=%2d,key=%2d
",x,ch[x][0],ch[x][1],pre[x],size[x],key[x]);
Treavel(ch[x][1]);
}
}
void debug(int rp)
{
printf("root:%d
",rp);
Treavel(rp);
}
void newnode(int &x,int fa,int vul){
x=++cnt;
key[x]=vul;size[x]=1;pre[x]=fa;
ch[x][0]=ch[x][1]=0;
}
void up(int x){
size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}
void rotate(int x,int kind){
int y=pre[x];
ch[y][!kind]=ch[x][kind];
pre[ch[x][kind]]=y;
if(pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x;
pre[x]=pre[y];ch[x][kind]=y;pre[y]=x;
up(y);up(x);
}
void splay(int x,int goal){
while(pre[x]!=goal){
if(pre[pre[x]]==goal){
rotate(x,ch[pre[x]][0]==x);
}
else{
int y=pre[x];
int kind=ch[pre[y]][0]==y;
if(ch[y][kind]==x){
rotate(x,!kind);rotate(x,kind);
}
else{
rotate(y,kind);rotate(x,kind);
}
}
}
if(goal==0) root=x;
up(x);
}
int find1(int x,int t){
if(t==size[ch[x][0]]+1) return x;
else if(t<=size[ch[x][0]]) return find1(ch[x][0],t);
else return find1(ch[x][1],t-size[ch[x][0]]-1);
}
void insert(int pos,int vul){
splay(find1(root,pos),0);
splay(find1(root,pos+1),root);
newnode(rl,ch[root][1],vul);
up(ch[root][1]);up(root);
}
int querty(int pos){
return key[find1(root,pos+1)];
}
void built(int &x,int l,int r,int fa){
if(l>r) return ;
int mid=(l+r)>>1;
newnode(x,fa,a[mid]);
built(ch[x][0],l,mid-1,x);
built(ch[x][1],mid+1,r,x);
up(x);
}
void inte(){
cnt=root=0;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
newnode(root,0,0);
newnode(ch[root][1],root,0);
built(rl,1,n,ch[root][1]);
up(ch[root][1]);up(root);
}
int main(){
ios::sync_with_stdio(false);
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
scanf("%d",&n);
inte();
int op,l,r,c;
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&op,&l,&r,&c);
if(op==0) insert(l,r);
else printf("%d
",querty(r));
}
return 0;
}