#include<algorithm>
#include<cstdio>
int i,n,t,wi,a[100005],Q[100005],W[100005];
long long ans;
int main(){
while(scanf("%d",&n)!=EOF){
if(!n)break;
for(i=1;i<=n;i++)scanf("%d",&a[i]);
ans=a[n+1]=t=0;
for(i=1;i<=n+1;i++)
if(a[i]>Q[t])Q[++t]=a[i],W[t]=1;
else{
wi=0;
while(t&&a[i]<=Q[t])ans=std::max(ans,(long long)(wi+=W[t])*Q[t--]);
Q[++t]=a[i],W[t]=wi+1;
}
printf("%lld\n",ans);
}
}
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e6+5;
int m,x,tl,tr,L[N],R[N],f[N],s[N];char a;
int main(){
while(scanf("%d",&m)!=EOF){
s[0]=0;f[0]=-0xfffffff;tl=tr=0;
while(m--){
cin>>a;
if(a=='I'){
scanf("%d",&x);
L[++tl]=x;
f[tl]=max(f[tl-1],s[tl]=s[tl-1]+x);
}
else if(a=='R'){
if(tr){
x=L[++tl]=R[tr--];
f[tl]=max(f[tl-1],s[tl]=s[tl-1]+x);
}
}
else if(a=='Q')scanf("%d",&x),printf("%d\n",f[x]);
else if(a=='L'){if(tl)R[++tr]=L[tl--];}
else if(tl)tl--;
}
}
}
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#define LL long long
using namespace std;
int n,f,t1,t2,i,power[300],ch[40];
LL x,sum[40];string a;
LL mi(LL x,LL k){
LL s=1;
while(k){
if(k&1)s=(s*x);
x=(x*x);k>>=1;
}
return s;
}
inline void pop(char fh){
t1--;t2--;
if(fh=='+')sum[t1]+=sum[t1+1];
if(fh=='-')sum[t1]-=sum[t1+1];
if(fh=='*')sum[t1]*=sum[t1+1];
if(fh=='/')sum[t1]/=sum[t1+1];
if(fh=='^')sum[t1]=mi(sum[t1],sum[t1+1]);
}
int main(){
cin>>a;a='('+a+')';n=a.size();
power['(']=0;power['+']=power['-']=1;power['*']=power['/']=2;power['^']=3;
while(i<n){
x=0,f=0;
while(isdigit(a[i]))x=x*10+a[i++]-'0',f=1;
if(f)sum[++t1]=x;
if(a[i]=='(')ch[++t2]=a[i++];
if(a[i]==')'){
while(ch[t2]!='(')pop(ch[t2]);
i++;t2--;
}
if(power[a[i]]){
if(a[i]=='-'&&a[i-1]=='('){
x=0,i++;
while(isdigit(a[i]))x=x*10+a[i++]-'0';
sum[++t1]=-x;
}
else {
while(power[a[i]]<=power[ch[t2]])pop(ch[t2]);
ch[++t2]=a[i++];
}
}
}
while(t2)pop(ch[t2]);
printf("%lld",sum[1]);
}
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=7100005;
int A[N],B[N],C[N],ans[N],h1,t1,h2,t2,h3,t3,s[100005],tmp,re,x,i,n,m,q,u,v,t;
double p;
inline int f(){
int a=-0xfffffff;
if(h1<=t1)a=max(a,A[h1]);
if(h2<=t2)a=max(a,B[h2]);
if(h3<=t3)a=max(a,C[h3]);
if(h1<=t1&&a==A[h1])h1++;
else if(h2<=t2&&a==B[h2])h2++;
else h3++;
return a;
}
inline bool cmp(int a,int b){return a>b;}
int main(){
scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
p=1.0*u/v;h1=h2=h3=1;
for(i=1;i<=n;i++)scanf("%d",&s[i]);
sort(s+1,s+n+1,cmp);
for(i=1;i<=n;i++)A[++t1]=s[i];
for(i=1;i<=m;i++){
x=f();
x+=tmp;
if(i%t==0)printf("%d ",x);
re=p*x;
B[++t2]=re-tmp-q;
C[++t3]=x-re-tmp-q;
tmp+=q;
}
printf("\n");
for(i=h1;i<=t1;i++)ans[++ans[0]]=A[i];
for(i=h2;i<=t2;i++)ans[++ans[0]]=B[i];
for(i=h3;i<=t3;i++)ans[++ans[0]]=C[i];
sort(ans+1,ans+ans[0]+1,cmp);
for(i=1;i<=ans[0];i++)
if(i%t==0)printf("%d ",ans[i]+tmp);
return 0;
}
#include<algorithm>
#include<cstdio>
const int N=1e6+5;
int n,k,i,h,t,a[N],Q[N],D[N];
int main(){
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
while(h<=t&&Q[t]>=a[i])t--;Q[++t]=a[i],D[t]=i;
while(h<t&&D[h]+k-1<i)h++;
if(i>=k)printf("%d ",Q[h]);
}
printf("\n");h=t=0;
for(i=1;i<=n;i++){
while(h<=t&&Q[t]<=a[i])t--;Q[++t]=a[i],D[t]=i;
while(h<t&&D[h]+k-1<i)h++;
if(i>=k)printf("%d ",Q[h]);
}
}
#include<bits/stdc++.h>
#define itn int
#define mian main
using namespace std;
int len,a[30005],piu,op;
char s;
priority_queue<int,vector<int>, greater<int> >sak;
priority_queue<int,vector<int>,less<int> >b;
int main(){
while(scanf("%c",&s)){
if(s=='A'){
while(s!='(') scanf("%c",&s);
scanf("%d",&a[++len]);
getchar();
piu++;
}
if(s=='G'){
getchar();
getchar();
while(op<piu){
op++;
b.push(a[op]);
sak.push(b.top());
b.pop();
}
printf("%d ",sak.top());
b.push(sak.top());
sak.pop();
}
getchar();
}
return 0;
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstdio>
#define LL long long
#define Re register LL
using namespace std;
LL ans,fu,S,d,k,n,t,i,x;
struct QAQ{LL x,d;inline bool operator<(QAQ b)const{return x==b.x?d<b.d:x<b.x;}}Q[100011];
inline void up(Re p){
while(p>1)
if(Q[p]<Q[p>>1])swap(Q[p],Q[p>>1]),p>>=1;
else break;
}
inline void down(Re p){
int s=p<<1;
while(s<=t){
if(s<t&&Q[s|1]<Q[s])s++;
if(Q[s]<Q[p])swap(Q[s],Q[p]),p=s,s<<=1;
else break;
}
}
inline void push(Re x,Re d){Q[++t].x=x,Q[t].d=d;up(t);}
inline void delet(Re p){swap(Q[p],Q[t--]);down(p);}
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
if(fu)x=-x;
}
int main(){
in(n),in(k);
while(n--)in(x),push(x,0);
while((t-1)%(k-1))push(0,0);
while(t>1){
x=k,S=0,d=0;
while(x--)d=max(d,Q[1].d),S+=Q[1].x,delet(1);
ans+=S,push(S,d+1);
}
printf("%lld\n%lld",ans,Q[1].d);
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
struct QAQ{int w,d;}a[10003];
int ans,n,i;
inline bool cmp(QAQ a,QAQ b){return a.d!=b.d?a.d<b.d:a.w>b.w;}
struct QWQ{
int heap[10003],t;
inline void CL(){memset(heap,0,sizeof(heap));t=0;}
inline void up(int p){
while(p>1)
if(heap[p>>1]>heap[p])swap(heap[p],heap[p>>1]),p>>=1;
else break;
}
inline void down(int p){
int s=(p<<1);
while(s<=t){
if(s<t&&heap[s]>heap[s|1])s++;
if(heap[s]<heap[p]){
swap(heap[s],heap[p]);
p=s,s<<=1;
}
else break;
}
}
inline void pop(){delet(1);}
inline int top(){return heap[1];}
inline int size(){return t;}
inline void push(int x){heap[++t]=x;up(t);}
inline void delet(int p){swap(heap[p],heap[t--]);down(p);}
}Q;
int main(){
while(scanf("%d",&n)!=EOF){
for(i=1;i<=n;i++)scanf("%d%d",&a[i].w,&a[i].d);
sort(a+1,a+n+1,cmp);ans=0;Q.CL();
for(i=1;i<=n;i++)
if(Q.size()<a[i].d)Q.push(a[i].w);
else if(Q.top()<a[i].w)Q.pop(),Q.push(a[i].w);
while(Q.size())ans+=Q.top(),Q.pop();
printf("%d\n",ans);
}
}
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
deque<int> dq;
int n = nums.size();
for (int i = 0; i < n; ++i) {
while (!dq.empty() && dq.front() < i - k + 1) {
dq.pop_front();
}
while (!dq.empty() && nums[i] >= nums[dq.back()]) {
dq.pop_back();
}
dq.push_back(i);
if (i >= k - 1) {
res.push_back(nums[dq.front()]);
}
}
return res;
}// 单调栈:寻找每个元素右侧第一个比它大的元素
vector<int> nextGreaterElement(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, -1);
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && nums[i] > nums[st.top()]) {
res[st.top()] = nums[i];
st.pop();
}
st.push(i);
}
return res;
}vector<int> fd(N, 0);
int find(int num) {
if (fd[num] == num) {
return num;
} else {
return fd[num] = find(fd[num]);
}
}class DSU {
private:
vector<int> parent;
vector<int> rank;
public:
DSU(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
void init(){
for (int i = 0; i < parent.size(); ++i) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (rank[x] < rank[y]) {
parent[x] = y;
} else {
parent[y] = x;
if (rank[x] == rank[y]) {
rank[x]++;
}
}
}
bool isConnected(int x, int y) {
return find(x) == find(y);
}
};#include<cstdio>
#define Re register int
const int N=1e4+3;
int n,x,y,T,op,fa[N],deep[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline int find(Re x){return x==fa[x]?x:find(fa[x]);}
inline void merge(Re x,Re y){
x=find(x),y=find(y);
if(x==y)return;
if(deep[x]==deep[y])++deep[fa[x]=y];
else if(deep[x]>deep[y])fa[y]=x;
else fa[x]=y;
}
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)fa[i]=i;
while(T--){
in(op),in(x),in(y);
if(op<2)merge(x,y);
else puts(find(x)==find(y)?"Y":"N");
}
}
#include<algorithm>
#include<cstdio>
#define Re register int
const int N=1e4+3;
int n,x,y,T,op,fa[N],size[N],deep[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline int find(Re x){return x==fa[x]?x:find(fa[x]);}
inline void merge(Re x,Re y){
x=find(x),y=find(y);
if(x==y)return;
if(size[x]>size[y])std::swap(x,y);
fa[x]=y,size[y]+=size[x];
}
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)fa[i]=i,size[i]=1;
while(T--){
in(op),in(x),in(y);
if(op<2)merge(x,y);
else puts(find(x)==find(y)?"Y":"N");
}
}
#include<cstdio>
#define Re register int
const int N=1e4+3;
int n,x,y,T,op,fa[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)fa[i]=i;
while(T--){
in(op),in(x),in(y);
if(op<2){if(find(x)!=find(y))fa[find(x)]=find(y);}
else puts(find(x)==find(y)?"Y":"N");
}
}
#include<cstdio>
#include<iostream>
using namespace std;// 找图的最小环
int minn=0x7fffff,n,f[200005],d[200005];
inline int min(int a,int b){if(a>b) return b;else return a;}
inline int find(int x){
if(f[x]!=x){
int l=f[x];
f[x]=find(f[x]);
d[x]+=d[l];
}
return f[x];
}
inline void sakura(int a,int b){
int aa=find(a);int bb=find(b);
if(aa!=bb){
f[aa]=bb;
d[a]=d[b]+1;
}
else
minn=min(minn,d[a]+d[b]+1);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
sakura(i,x);
}
printf("%d",minn);
return 0;
}
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int fa[1001],n,k;
struct sakura{int u,v,next;}sak[4001];
int st[1001],tot=0;
int p[1001],pp[1001];
void add(int x,int y){
tot++;
sak[tot].u=x;
sak[tot].v=y;
sak[tot].next=st[x];
st[x]=tot;
}
int find(int x){
if (fa[x]!=x)
fa[x]=find(fa[x]);
return fa[x];
}
void unionn(int r1,int r2){
fa[r1]=r2;
}
void doit(){
int i,j;
for (i=n-1;i>=1;i--){
pp[i]=1;
for (j=st[i];j;j=sak[j].next){
if (pp[sak[j].v]){
int r1=find(sak[j].u);
int r2=find(sak[j].v);
if (r1!=r2){
unionn(r1,r2);
p[r1]+=p[r2];
p[r2]=p[r1];
}
}
}
if (p[find(i)]>(n+1)/2){
printf("%d",i);
}
}
}
int main(){
scanf("%d",&n);
pp[n]=1;
for (int i=1;i<=n;i++){
scanf("%d",&k);
fa[i]=i;
p[i]=1;
for (int j=1;j<=k;j++){
int x;
scanf("%d",&x);
add(i,x);
}
}
doit();
return 0;
}
#include<bits/stdc++.h>
using namespace std;
struct T{int x,y;}f[210][210];
int x,y,n,m;char c;T a1,a2;
T s(int x,int y){
while((x==f[x][y].x)&&(y==f[x][y].y))return f[x][y];
return s(f[x][y].x,f[x][y].y);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j].x=i,f[i][j].y=j;
for(int i=1;i<=m;i++)
{
cin>>x>>y>>c;
if(c=='D')a1=s(x,y),a2=s(x+1,y);
else a1=s(x,y),a2=s(x,y+1);
if(a1.x==a2.x&&a1.y==a2.y){
printf("%d\n",i);return 0;
}
else f[a2.x][a2.y]=a1;
}
printf("draw");
return 0;
}
/*
����
| |
| |
| |
������ ������
| ����ACʮ�ּ� |
������ ������
| |
| |
| |
����
*/
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
int n,m,k,f[40001],sum;
struct sakura{
int p,a,b,val;
}sak[40001];
inline int find(int x){return f[x]==x?x:find(f[x]);}
inline bool cmp(const sakura &a,const sakura &b){return a.val<b.val;}
inline bool unions(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy) return 0;
else f[fy]=fx;
return 1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&sak[i].a,&sak[i].b,&sak[i].val);
std::sort(sak+1,sak+1+m,cmp);
for(int i=1;i<=m;i++){
if(unions(sak[i].a,sak[i].b)){
k++;
sum=sak[i].val;
}
if(k==n-1) break;
}
printf("%d %d",n-1,sum);
return 0;
}
#include<algorithm>
#include<cstdlib>
#include<cstdio>
int g,i,j,n,m,p,x,y,c,ans,k,f[2010];
struct QAQ{int l,r,w;}a[40010];
inline int fi(int x){if(x!=f[x])f[x]=fi(f[x]);return f[x];}
inline int cmp(const QAQ &a,const QAQ &b){return a.w<b.w;}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)f[i]=i;
for(i=1;i<=m;i++){
scanf("%d%d%d%d",&p,&x,&y,&c);
if(p==1){ans+=c,f[fi(y)]=fi(x);}
else a[++g].l=x,a[g].r=y,a[g].w=c;
}
std::sort(a+1,a+g+1,cmp);
for(i=1;i<=g;i++){
x=fi(a[i].l),y=fi(a[i].r);
if(x!=y){
f[y]=x;k++;
ans+=a[i].w;
}
}
printf("%d",ans);
return 0;
}
template<class T> struct BIT {
int n;
vector<T> w;
BIT(int n, auto &in) : n(n), w(n + 1) { // 预处理填值
for (int i = 1; i <= n; i++) {
add(i, in[i]);
}
}
void add(int x, T v) {
for (; x <= n; x += x & -x) {
w[x] += v;
}
}
T ask(int x) { // 前缀和查询
T ans = 0;
for (; x; x -= x & -x) {
ans += w[x];
}
return ans;
}
T ask(int l, int r) { // 差分实现区间和查询
return ask(r) - ask(l - 1);
}
};/*
n n
S[x]= (x+1)*��A[i] - ��i*A[i]
i=1 i=1
*/
#include<cstdio>
#define LL long long
#define Re register int
const int N=1e6+3;
int n,x,y,z,T,op;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct BIT{
LL C1[N],C2[N];
inline void add(Re x,Re v){Re i=x;while(i<=n)C1[i]+=v,C2[i]+=(LL)x*v,i+=i&-i;}
inline void add(Re L,Re R,Re v){add(L,v),add(R+1,-v);}
inline LL ask(Re x){Re i=x;LL ans=0;while(i)ans+=(x+1)*C1[i]-C2[i],i-=i&-i;return ans;}
inline LL ask(Re L,Re R){return ask(R)-ask(L-1);}
}TR;
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)in(x),TR.add(i,i,x);
while(T--){
in(op),in(x),in(y);
if(op<2)in(z),TR.add(x,y,z);
else printf("%lld\n",TR.ask(x,y));
}
}
#include<cstdio>
#define LL long long
#define Re register int
const int N=5e5+3;
int n,x,y,z,T,op;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct BIT{
LL C[N];
inline void add(Re x,Re v){while(x<=n)C[x]+=v,x+=x&-x;}
inline void add(Re L,Re R,Re v){add(L,v),add(R+1,-v);}
inline LL ask(Re x){LL ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
}TR;
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)in(x),TR.add(i,i,x);
while(T--){
in(op),in(x);
if(op<2)in(y),in(z),TR.add(x,y,z);
else printf("%lld\n",TR.ask(x));
}
}
#include<cstdio>
#define LL long long
#define Re register int
const int N=5e5+3;
int n,x,y,T,op;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct BIT{
LL C[N];
inline void add(Re x,Re v){while(x<=n)C[x]+=v,x+=x&-x;}
inline LL ask(Re x){LL ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
inline LL ask(Re L,Re R){return ask(R)-ask(L-1);}
}TR;
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)in(x),TR.add(i,x);
while(T--){
in(op),in(x),in(y);
if(op<2)TR.add(x,y);
else printf("%ld\n",TR.ask(x,y));
}
}
/*
n m n m n m n m
s[x][y]=(x+1)*(y+1)*�� ��a[i][j] - (y+1)*�� ��a[i][j]*i - (x+1)*�� ��a[i][j]*j + �� ��a[i][j]*i*j
i=1 j=1 i=1 j=1 i=1 j=1 i=1 j=1
*/
#include<cstdio>
#define y1 yyyy
#define LL long long
#define Re register int
const int N=2048+3;
int n,m,x,x1,y1,x2,y2,op;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct BIT{
LL C1[N][N],C2[N][N],C3[N][N],C4[N][N];
inline void add(Re x,Re y,Re v){
Re i=x;
while(i<=n){
Re j=y;
while(j<=m)C1[i][j]+=v,C2[i][j]+=(LL)x*v,C3[i][j]+=(LL)y*v,C4[i][j]+=(LL)x*y*v,j+=j&-j;
i+=i&-i;
}
}
inline void add(Re x1,Re y1,Re x2,Re y2,Re z){
add(x1,y1,z),add(x1,y2+1,-z),add(x2+1,y1,-z),add(x2+1,y2+1,z);
}
inline LL ask(Re x,Re y){
Re i=x;LL ans=0;
while(i){
Re j=y;
while(j)ans+=(LL)(x+1)*(y+1)*C1[i][j]-(LL)(y+1)*C2[i][j]-(LL)(x+1)*C3[i][j]+C4[i][j],j-=j&-j;
i-=i&-i;
}
return ans;
}
inline LL ask(Re x1,Re y1,Re x2,Re y2){
return ask(x2,y2)-ask(x2,y1-1)-ask(x1-1,y2)+ask(x1-1,y1-1);
}
}TR;
int main(){
in(n),in(m);
while(~scanf("%d",&op)){
in(x1),in(y1),in(x2),in(y2);
if(op<2)in(x),TR.add(x1,y1,x2,y2,x);
else printf("%lld\n",TR.ask(x1,y1,x2,y2));
}
}
/*
(样例输入)
输入:
2 3 8
1 1 2 2 3 2
1 1 1 2 2 -3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
输出
-3
-1
2
-3
-1
2
*/
#include<cstdio>
#define y1 yyyy
#define LL long long
#define Re register int
const int N=4096+3;
int n,m,T,x,x1,y1,x2,y2,op;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct BIT{
LL C[N][N];
inline void add(Re x,Re y,Re v){
while(x<=n){Re j=y;while(j<=m)C[x][j]+=v,j+=j&-j;x+=x&-x;}
}
inline void add(Re x1,Re y1,Re x2,Re y2,Re z){
add(x1,y1,z),add(x1,y2+1,-z),add(x2+1,y1,-z),add(x2+1,y2+1,z);
}
inline LL ask(Re x,Re y){
LL ans=0;
while(x){Re j=y;while(j)ans+=C[x][j],j-=j&-j;x-=x&-x;}
return ans;
}
}TR;
int main(){
in(n),in(m),in(T);
while(T--){
in(op),in(x1),in(y1);
if(op<2)in(x2),in(y2),in(x),TR.add(x1,y1,x2,y2,x);
else printf("%lld\n",TR.ask(x1,y1));
}
}
#include<cstdio>
#define y1 yyyy
#define LL long long
#define Re register int
const int N=4096+3;
int n,m,x1,y1,x2,y2,op;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct BIT{
LL C[N][N];
inline void add(Re x,Re y,Re v){
while(x<=n){Re j=y;while(j<=m)C[x][j]+=v,j+=j&-j;x+=x&-x;}
}
inline LL ask(Re x,Re y){
LL ans=0;
while(x){Re j=y;while(j)ans+=C[x][j],j-=j&-j;x-=x&-x;}
return ans;
}
inline LL ask(Re x1,Re y1,Re x2,Re y2){return ask(x2,y2)-ask(x2,y1-1)-ask(x1-1,y2)+ask(x1-1,y1-1);}
}TR;
int main(){
in(n),in(m);
while(~scanf("%d",&op)){
in(x1),in(y1),in(x2);
if(op<2)TR.add(x1,y1,x2);
else in(y2),printf("%lld\n",TR.ask(x1,y1,x2,y2));
}
}
#include<cstdio>
#define LL long long
#define Re register int
const int N=1e5+3;
int n,x,y,T,A[N];
inline void in(Re &x){
int f=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;
}
inline int max(Re a,Re b){return a>b?a:b;}
struct BIT{
int C[N];
inline void add(Re x,Re v){while(x<=n)C[x]=max(C[x],v),x+=x&-x;}
inline int ask(Re l,Re r){
Re ans=0;
while(l<=r){
while(r-(r&-r)>=l)ans=max(ans,C[r]),r-=r&-r;
ans=max(ans,A[r--]);
}
return ans;
}
}TR;
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)in(A[i]),TR.add(i,A[i]);
while(T--)in(x),in(y),printf("%d\n",TR.ask(x,y));
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstdio>
#define Re register int
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
#define P(x) if(op[i]==x)
using namespace std;
const int N=1e5+3,inf=2147483647;
int m,T,fu,C[N],a[N],b[N],Q[N],op[N];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void add(Re x,Re v){while(x<=m)C[x]+=v,x+=x&-x;}
inline int ask(Re x){
Re ans=0;
while(x>0)ans+=C[x],x-=x&-x;
return ans;
}
inline int ask_kth(Re k){
Re l=0,r=m;
while(l<r){
Re mid=l+r>>1;
if(ask(mid)>=k)r=mid;
else l=mid+1;
}
return b[l];
}
int main(){
in(T);
F(i,1,T){
in(op[i]),in(Q[i]);
if(op[i]!=4)b[++m]=Q[i];
}
sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
F(i,1,T){
P(1)add(lo(Q[i]),1);
P(2)add(lo(Q[i]),-1);
P(3)printf("%d\n",ask(lo(Q[i])-1)+1);
P(4)printf("%d\n",ask_kth(Q[i]));
P(5)printf("%d\n",ask_kth(ask(lo(Q[i])-1)));
P(6)printf("%d\n",ask_kth(ask(lo(Q[i]))+1));
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#define LL long long
#define Re register LL
#define F(a,b) for(i=a;i<=b;++i)
const int N=5e5+3,Np=2e7;
LL i,j,n,x,l,r,K,T,fu,cnt,c[N],C[N],pan[Np+1],pri[Np+1],phi[Np+1];char ch;
inline void in(Re &x){
x=fu=0;ch=getchar();
while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x=fu?-x:x;
}
inline void add(Re x,Re k){while(x<=n)C[x]+=k,x+=x&-x;}
inline LL ask(Re x){Re tmp=0;while(x)tmp+=C[x],x-=x&-x;return tmp;}
inline LL mi(Re x,Re k,Re P){
Re s=1,ok=0,flag=0;ok|=(x>=P);x%=P;
while(k){
if(k&1){s*=x;flag|=(ok||s>=P);s%=P;}
x*=x;ok|=(x>=P);x%=P;k>>=1;
}
return s+(flag?P:0);
}
inline LL sakura(Re l,Re r,Re P){
if(P==1|l>r)return 1;
return mi(ask(l),sakura(l+1,r,phi[P]),P);
}
int main(){
for(i=2;i<=Np;++i){
if(!pan[i])pri[++cnt]=i,phi[i]=i-1;
for(j=1;j<=cnt;++j){
if(i*pri[j]>Np)break;
pan[i*pri[j]]=1;
if(i%pri[j])phi[i*pri[j]]=phi[i]*(pri[j]-1);
else{phi[i*pri[j]]=phi[i]*pri[j];break;}
}
}
in(n),in(T);
F(1,n)in(x),add(i,x-l),l=x;
while(T--){
in(K),in(l),in(r),in(x);
if(K<2)add(l,x),add(r+1,-x);
else printf("%lld\n",sakura(l,r,x)%x);
}
}
struct node{
int data,lazy;
};
void build(const vector<int>&datas,vector<node>&tree,int rt,int left,int right){
if(left == right){
tree[rt].data=datas[left];
return;
}
int mid = left+(right-left)/2;
build(datas,tree,2*rt,left,mid);
build(datas,tree,2*rt+1,mid+1,right);
tree[rt].data = tree[2*rt].data+tree[2*rt+1].data;
}
void pushDown(vector<node>&tree,int rt, int len){
if(tree[rt].lazy != 0){
tree[rt*2].data += tree[rt].lazy * (len - len/2);
tree[rt*2].lazy += tree[rt].lazy;
tree[rt*2+1].data += tree[rt].lazy * (len/2);
tree[rt*2+1].lazy += tree[rt].lazy;
tree[rt].lazy = 0;
}
}
int query(vector<node>&tree,int rt,int left,int right,int ql,int qr){
if(ql > right || qr < left){
return MIN;
}
if(ql <= left && qr >= right){
return tree[rt].data;
}
int mid = left+(right-left)/2;
pushDown(tree,rt,right-left+1);
int leftsum = query(tree,2*rt,left,mid,ql,qr);
int rightsum = query(tree,2*rt+1,mid+1,right,ql,qr);
return leftsum+rightsum;
}
void updata(vector<node>&tree,int rt,int left,int right,int idx,int value){
if(left == right){
tree[rt].data = value;
tree[rt].lazy = 0;
return;
}
int mid = left+(right-left)/2;
pushDown(tree,rt,right-left+1);
if(idx<=mid){
updata(tree,2*rt,left,mid,idx,value);
}else{
updata(tree,2*rt+1,mid+1,right,idx,value);
}
tree[rt].data = tree[2*rt].data+tree[2*rt+1].data;
}
void updataRange(vector<node>&tree,int rt,int left,int right,int ul,int ur,int value){
if(ul>right||ur<left) return;
if(ul<=left && ur >= right){
tree[rt].data += value * (right - left + 1);
tree[rt].lazy += value;
return;
}
int mid = left+(right-left)/2;
pushDown(tree,rt,right-left+1);
updataRange(tree,2*rt,left,mid,ul,ur,value);
updataRange(tree,2*rt+1,mid+1,right,ul,ur,value);
tree[rt].data=tree[2*rt].data+tree[2*rt+1].data;
}template<class Info, class Tag> struct LazySegmentTree {
int n;
vector<Info> info;
vector<Tag> tag;
LazySegmentTree(vector<Info> init) {
n = init.size();
info.assign(4 * n, Info());
tag.assign(4 * n, Tag());
function<void(int, int, int)> build = [&](int p, int l, int r) {
if (l == r) {
info[p] = init[l - 1];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m + 1, r);
pull(p);
};
build(1, 1, n);
}
void pull(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void apply(int p, const Tag &v) {
info[p].apply(v);
tag[p].apply(v);
}
void push(int p) {
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
if (l > y || r < x) return;
if (l >= x && r <= y) {
apply(p, v);
return;
}
push(p);
int m = (l + r) / 2;
rangeApply(2 * p, l, m, x, y, v);
rangeApply(2 * p + 1, m + 1, r, x, y, v);
pull(p);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l > y || r < x) return Info();
if (l >= x && r <= y) return info[p];
push(p);
int m = (l + r) / 2;
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m + 1, r, x, y);
}
};
struct Tag {
LL x;
Tag(LL x = 0) { this->x = x; }
void apply(const Tag &t) { x += t.x; }
};
struct Info {
LL x, l, r;
Info(LL x = 0, LL l = 0, LL r = 0) { this->x = x; this->l = l; this->r = r; }
void apply(const Tag &t) { if (t.x) x += t.x * (r - l + 1); }
};
Info operator+(const Info &a, const Info &b) { return Info(a.x + b.x, a.l, b.r); }struct tnode {
int l, r;
int mins;
};
struct Segment {
tnode t[4 * N];
int fa[4 * N];
void built(int root, int l, int r) {
"""
构建线段树
:param root: 当前节点
:param l: 左端点
:param r: 右端点
"""
t[root].l = l;
t[root].r = r;
if (l == r) {
t[root].mins = 0;
fa[l] = root;
return;
}
int ch = root << 1;
int mid = (l + r) >> 1;
built(ch, l, mid);
built(ch + 1, mid + 1, r);
t[root].mins = min(t[ch].mins, t[ch + 1].mins);
}
void modify(int num, int pos) {
"""
修改线段树
:param num: 要修改的位置
:param pos: 要修改的值
"""
int root = fa[num];
t[root].mins = pos;
root >>= 1;
while (root) {
int ch = root << 1;
t[root].mins = min(t[ch].mins, t[ch + 1].mins);
root >>= 1;
}
}
int query(int l) {
"""
查询线段树
:param l: 查询的左端点
:return: 最小的未被覆盖的位置
"""
int root = 1;
while (t[root].l != t[root].r) {
int ch = root << 1;
if (t[ch].mins >= l) {
root = ch + 1;
} else {
root = ch;
}
}
return t[root].l - 1;
}
} ST;
// int main() {
// // 初始化线段树,假设值范围是1到n
// int n;
// cin >> n;
// ST.built(1, 1, n);
// // 示例:处理m次操作
// int m;
// cin >> m;
// while (m--) {
// int op, x, y;
// cin >> op;
// if (op == 1) {
// cin >> x >> y;
// ST.modify(x, y);
// } else if (op == 2) {
// cin >> x;
// cout << ST.query(x) << '\n';
// }
// }
// }#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1e5+3,inf=2147483647;
int i,j,n,k,m,a[N],lg[N],f1[N][18],f2[N][18];
int main(){
scanf("%d%d",&n,&k);
for(i=0;i<=17;i++)
for(j=0;j<=n+1;j++)
f1[i][j]=-inf,f2[i][j]=inf;
lg[1]=0;for(i=2;i<=n;i++)lg[i]=lg[i>>1]+1;m=lg[n];
for(i=1;i<=n;f2[i][0]=f1[i][0],i++)scanf("%d",&f1[i][0]);
for(i=1;i<=m;i++)
for(j=1;j+(1<<i)-1<=n;j++)
f1[j][i]=max(f1[j][i-1],f1[j+(1<<i-1)][i-1]),f2[j][i]=min(f2[j][i-1],f2[j+(1<<i-1)][i-1]);
m=lg[k];
for(i=1;i+k-1<=n;i++)printf("%d %d\n",max(f1[i][m],f1[i+k-(1<<m)][m]),min(f2[i][m],f2[i+k-(1<<m)][m]));
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=3e5+5,logN=19;
int n;char s[N];
inline void in(Re &x){
Re f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Suffix_Array{
int m,x[N],y[N],SA[N],cnt[N],rank[N],Height[N];
inline void get_SA(){
m=129;
for(Re i=1;i<=n;++i)++cnt[x[i]=s[i]];
for(Re i=2;i<=m;++i)cnt[i]+=cnt[i-1];
for(Re i=n;i>=1;--i)SA[cnt[x[i]]--]=i;
for(Re len=1;len<=n;len<<=1){
Re t=0;
for(Re i=n-len+1;i<=n;++i)y[++t]=i;
for(Re i=1;i<=n;++i)if(SA[i]>len)y[++t]=SA[i]-len;
for(Re i=1;i<=m;++i)cnt[i]=0;
for(Re i=1;i<=n;++i)++cnt[x[i]];
for(Re i=2;i<=m;++i)cnt[i]+=cnt[i-1];
for(Re i=n;i>=1;--i)SA[cnt[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y),x[SA[1]]=m=1;
for(Re i=2;i<=n;++i)
x[SA[i]]=(y[SA[i]]==y[SA[i-1]]&&y[SA[i]+len]==y[SA[i-1]+len])?m:++m;
if(m>=n)break;
}
}
inline void get_Height(){
for(Re i=1;i<=n;++i)rank[SA[i]]=i;
for(Re i=1,k=0;i<=n;++i){
if(rank[i]==1)continue;
if(k)--k;
Re j=SA[rank[i]-1];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])++k;
Height[rank[i]]=k;
}
// for(Re i=1;i<=n;++i)printf("%d ",Height[i]);puts("");
}
int lg[N],dp[N][20];
inline void get_ST(){
lg[0]=-1;
for(Re i=1;i<=n;++i)dp[i][0]=Height[i],lg[i]=lg[i>>1]+1;
for(Re j=1;j<=logN;++j)
for(Re i=1;i+(1<<j)-1<=n;++i)
dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}
inline int ask_min(Re l,Re r){
Re m=lg[r-l+1];
return min(dp[l][m],dp[r-(1<<m)+1][m]);
}
int r[N<<1];char a[N<<1];LL ans;
inline void check(Re x,Re len){
// printf("x=%d, len=%d\n",x,len);
x=rank[x];Re L=x,R=x;
if(Height[x]>=len){
Re l=2,r=x;
while(l<r){
Re mid=l+r>>1;
if(ask_min(mid,x)>=len)r=mid;
else l=mid+1;
}
L=r-1;
}
if(Height[x+1]>=len){
Re l=x+1,r=n;
while(l<r){
Re mid=l+r+1>>1;
if(ask_min(x+1,mid)>=len)l=mid;
else r=mid-1;
}
R=l;
}
ans=max(ans,(LL)len*(R-L+1));
}
inline void sakura(){
get_SA(),get_Height(),get_ST();
a[m=0]='$',a[++m]='|';
for(Re i=1;i<=n;++i)a[++m]=s[i],a[++m]='|';
for(Re i=1,R=0,mid=0;i<=m;++i){
r[i]=i<=R?min(r[(mid<<1)-i],R-i+1):1;
while(a[i-r[i]]==a[i+r[i]]){
++r[i];
if(i+r[i]-1>R)check((i>>1)-(r[i]>>1)+1,r[i]-!(i+r[i]&1));
}
if(i+r[i]-1>R)mid=i,R=i+r[i]-1;
}
// for(Re i=1;i<=m;++i)printf("%d ",r[i]);puts("");
printf("%lld\n",ans);
}
}SA;
int main(){
// freopen("123.txt","r",stdin);
// freopen("my.txt","w",stdout);
scanf("%s",s+1),n=strlen(s+1),SA.sakura();
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int n,m,x,y,o,cnt,k[N],A[N],B[N],pt[N],head[N];LL b[N],dp[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl tr[p].lp
#define pr tr[p].rp
#define mid ((L+R)>>1)
int O;
struct QAQ{int id,lp,rp;}tr[N*18*2*2];
inline LL y(Re id,Re x){return (LL)k[id]*x+b[id];}
inline void change(Re &p,Re L,Re R,Re id){
if(!p){tr[p=++O].id=id;return;}
if(L==R){if(y(id,L)<y(tr[p].id,L))tr[p].id=id;return;}
if(k[id]>k[tr[p].id]){
if(y(id,mid)<y(tr[p].id,mid))change(pr,mid+1,R,tr[p].id),tr[p].id=id;
else change(pl,L,mid,id);
}
else{
if(y(id,mid)<y(tr[p].id,mid))change(pl,L,mid,tr[p].id),tr[p].id=id;
else change(pr,mid+1,R,id);
}
}
inline LL ask(Re p,Re L,Re R,Re x){
if(!p)return 1e18;
if(L==R)return y(tr[p].id,x);
LL ans=y(tr[p].id,x);
if(x<=mid)return min(ans,ask(pl,L,mid,x));
else return min(ans,ask(pr,mid+1,R,x));
}
inline int merge(Re p,Re q,Re L,Re R){
if(!p||!q)return p+q;
if(L==R){if(y(tr[p].id,L)>y(tr[q].id,L))tr[p].id=tr[q].id;return p;}
pl=merge(pl,tr[q].lp,L,mid);
pr=merge(pr,tr[q].rp,mid+1,R);
change(p,L,R,tr[q].id);
return p;
}
}TR;
inline void dfs(Re x,Re fa){
Re son=0;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa)son=1,dfs(to,x),pt[x]=TR.merge(pt[x],pt[to],-N,N);
k[++cnt]=B[x],dp[x]=b[cnt]=son?TR.ask(pt[x],-N,N,A[x]):0;
TR.change(pt[x],-N,N,cnt);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),m=n-1;
for(Re i=1;i<=n;++i)in(A[i]);
for(Re i=1;i<=n;++i)in(B[i]);
while(m--)in(x),in(y),add(x,y),add(y,x);
dfs(1,0);
for(Re i=1;i<=n;++i)printf("%lld\n",dp[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2e5+3,logN=18;
int n,m,x,y,z,T,b[N],A[N],pt[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct President_Tree{
#define pl tr[p].lp
#define pr tr[p].rp
#define mid (L+R>>1)
int O;
struct QAQ{int S,lp,rp;}tr[N*(logN+1)];
inline void creat(Re &p,Re q,Re L,Re R,Re w){
p=++O,tr[p]=tr[q],++tr[p].S;
if(L==R)return;
if(w<=mid)creat(pl,tr[q].lp,L,mid,w);
else creat(pr,tr[q].rp,mid+1,R,w);
}
inline int ask(Re p,Re q,Re L,Re R,Re k){
if(L==R)return L;
Re tmp=tr[pl].S-tr[tr[q].lp].S;
if(tmp>=k)return ask(pl,tr[q].lp,L,mid,k);
else return ask(pr,tr[q].rp,mid+1,R,k-tmp);
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
sort(b+1,b+n+1),m=unique(b+1,b+n+1)-b-1;
for(Re i=1;i<=n;++i)T1.creat(pt[i],pt[i-1],1,m,lower_bound(b+1,b+m+1,A[i])-b);
while(T--)in(x),in(y),in(z),printf("%d\n",b[T1.ask(pt[y],pt[x-1],1,m,z)]);
}
#include<cstdio>
#define LL long long
#define Re register int
const int N=5e5+3;
int n,x,y,T;LL z,A[N];char op;
template<typename T>inline void in(T &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline LL abs(LL a){return a<0?-a:a;}
inline LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
struct BIT{
LL C[N];
inline void add(Re x,LL v){while(x<=n)C[x]+=v,x+=x&-x;}
inline void add(Re L,Re R,LL v){add(L,v),add(R+1,-v);}
inline LL ask(Re x){LL ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
}TR0;
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
LL tr[N<<2];
inline void pushup(Re p){tr[p]=gcd(tr[pl],tr[pr]);}
inline void build(Re p,Re L,Re R){
if(L==R){tr[p]=A[L]-A[L-1];return;}
build(pl,L,mid),build(pr,mid+1,R);
pushup(p);
}
inline void change(Re p,Re L,Re R,Re x,LL v){
if(L==R){tr[p]+=v;return;}
if(x<=mid)change(pl,L,mid,x,v);
else change(pr,mid+1,R,x,v);
pushup(p);
}
inline LL ask(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return abs(tr[p]);
if(r<=mid)return ask(pl,L,mid,l,r);
else if(l>mid)return ask(pr,mid+1,R,l,r);
else return gcd(ask(pl,L,mid,l,r),ask(pr,mid+1,R,l,r));
}
}TR;
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)in(A[i]),TR0.add(i,i,A[i]);
TR.build(1,1,n);
while(T--){
scanf(" %c",&op),in(x),in(y);
if(op=='Q')printf("%lld\n",gcd(TR0.ask(x),TR.ask(1,1,n,x+1,y)));
else{
in(z),TR0.add(x,y,z),TR.change(1,1,n,x,z);if(y<n)TR.change(1,1,n,y+1,-z);
}
}
}
#include<cstdio>
#define LL long long
#define Re register int
const int N=1e5+3;
int n,x,y,z,T,op,A[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
struct QAQ{LL S,add;}tr[N<<2];
inline void pushup(Re p){tr[p].S=tr[pl].S+tr[pr].S;}
inline void updata(Re p,Re L,Re R,LL v){tr[p].S+=v*(R-L+1),tr[p].add+=v;}
inline void pushdown(Re p,Re L,Re R){
if(tr[p].add)updata(pl,L,mid,tr[p].add),updata(pr,mid+1,R,tr[p].add),tr[p].add=0;
}
inline void build(Re p,Re L,Re R){
if(L==R){tr[p].S=A[L];return;}
build(pl,L,mid),build(pr,mid+1,R);
pushup(p);
}
inline void change(Re p,Re L,Re R,Re l,Re r,Re v){
if(l<=L&&R<=r){updata(p,L,R,v);return;}
pushdown(p,L,R);
if(l<=mid)change(pl,L,mid,l,r,v);
if(r>mid)change(pr,mid+1,R,l,r,v);
pushup(p);
}
inline LL ask(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return tr[p].S;
LL ans=0;pushdown(p,L,R);
if(l<=mid)ans+=ask(pl,L,mid,l,r);
if(r>mid)ans+=ask(pr,mid+1,R,l,r);
return ans;
}
}TR;
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)in(A[i]);
TR.build(1,1,n);
while(T--){
in(op),in(x),in(y);
if(op<2)in(z),TR.change(1,1,n,x,y,z);
else printf("%lld\n",TR.ask(1,1,n,x,y));
}
}
#include<cstdio>
#define LL long long
#define Re register int
const int N=1e5+3;
int n,x,y,z,T,P,op,A[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
struct QAQ{LL S,mul,add;}tr[N<<2];
inline void pushup(Re p){tr[p].S=(tr[pl].S+tr[pr].S)%P;}
inline void updata1(Re p,LL v){
tr[p].S=(LL)tr[p].S*v%P,tr[p].mul=(LL)tr[p].mul*v%P,tr[p].add=(LL)tr[p].add*v%P;
}
inline void updata2(Re p,Re L,Re R,LL v){(tr[p].S+=v*(R-L+1)%P)%=P,(tr[p].add+=v)%=P;}
inline void pushdown(Re p,Re L,Re R){
if(tr[p].mul!=1)updata1(pl,tr[p].mul),updata1(pr,tr[p].mul),tr[p].mul=1;
if(tr[p].add)updata2(pl,L,mid,tr[p].add),updata2(pr,mid+1,R,tr[p].add),tr[p].add=0;
}
inline void build(Re p,Re L,Re R){
tr[p].mul=1;
if(L==R){tr[p].S=A[L]%P;return;}
build(pl,L,mid),build(pr,mid+1,R);
pushup(p);
}
inline void change(Re p,Re L,Re R,Re l,Re r,Re v,Re op){
if(l<=L&&R<=r){if(op<2)updata1(p,v);else updata2(p,L,R,v);return;}
pushdown(p,L,R);
if(l<=mid)change(pl,L,mid,l,r,v,op);
if(r>mid)change(pr,mid+1,R,l,r,v,op);
pushup(p);
}
inline LL ask(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return tr[p].S;
LL ans=0;pushdown(p,L,R);
if(l<=mid)(ans+=ask(pl,L,mid,l,r))%=P;
if(r>mid)(ans+=ask(pr,mid+1,R,l,r))%=P;
return ans;
}
}TR;
int main(){
in(n),in(T),in(P);
for(Re i=1;i<=n;++i)in(A[i]);
TR.build(1,1,n);
while(T--){
in(op),in(x),in(y);
if(op<3)in(z),TR.change(1,1,n,x,y,z,op);
else printf("%lld\n",TR.ask(1,1,n,x,y));
}
}
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
#define div(a,b) floor((double)a/b)
using namespace std;
const int N=1e5+3;
int n,x,y,z,T,op,A[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
struct QAQ{LL S,add,min,max;}tr[N<<2];
inline void pushup(Re p){
tr[p].S=tr[pl].S+tr[pr].S;
tr[p].min=min(tr[pl].min,tr[pr].min);
tr[p].max=max(tr[pl].max,tr[pr].max);
}
inline void updata(Re p,Re L,Re R,LL v){tr[p].S+=v*(R-L+1),tr[p].add+=v,tr[p].min+=v,tr[p].max+=v;}
inline void pushdown(Re p,Re L,Re R){
if(tr[p].add)updata(pl,L,mid,tr[p].add),updata(pr,mid+1,R,tr[p].add),tr[p].add=0;
}
inline void build(Re p,Re L,Re R){
if(L==R){tr[p].S=tr[p].min=tr[p].max=A[L];return;}
build(pl,L,mid),build(pr,mid+1,R);
pushup(p);
}
inline void change(Re p,Re L,Re R,Re l,Re r,Re v){
if(l<=L&&R<=r){updata(p,L,R,v);return;}
pushdown(p,L,R);
if(l<=mid)change(pl,L,mid,l,r,v);
if(r>mid)change(pr,mid+1,R,l,r,v);
pushup(p);
}
inline void change_div(Re p,Re L,Re R,Re l,Re r,Re v){
if(l<=L&&R<=r&&(div(tr[p].max,v)-tr[p].max==div(tr[p].min,v)-tr[p].min)){
updata(p,L,R,div(tr[p].max,v)-tr[p].max);return;
}
pushdown(p,L,R);
if(l<=mid)change_div(pl,L,mid,l,r,v);
if(r>mid)change_div(pr,mid+1,R,l,r,v);
pushup(p);
}
inline LL ask_min(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return tr[p].min;
LL ans=1e18;pushdown(p,L,R);
if(l<=mid)ans=min(ans,ask_min(pl,L,mid,l,r));
if(r>mid)ans=min(ans,ask_min(pr,mid+1,R,l,r));
return ans;
}
inline LL ask_S(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return tr[p].S;
LL ans=0;pushdown(p,L,R);
if(l<=mid)ans+=ask_S(pl,L,mid,l,r);
if(r>mid)ans+=ask_S(pr,mid+1,R,l,r);
return ans;
}
}TR;
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)in(A[i]);
TR.build(1,1,n);
while(T--){
in(op),in(x),in(y),++x,++y;
if(op<2)in(z),TR.change(1,1,n,x,y,z);
else if(op<3)in(z),TR.change_div(1,1,n,x,y,z);
else if(op<4)printf("%lld\n",TR.ask_min(1,1,n,x,y));
else printf("%lld\n",TR.ask_S(1,1,n,x,y));
}
}
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int n,x,y,z,T,op;LL A[N];
template<typename T>inline void in(T &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
struct QAQ{LL S,max;}tr[N<<2];
inline void pushup(Re p){
tr[p].S=tr[pl].S+tr[pr].S;
tr[p].max=max(tr[pl].max,tr[pr].max);
}
inline void build(Re p,Re L,Re R){
if(L==R){tr[p].S=tr[p].max=A[L];return;}
build(pl,L,mid),build(pr,mid+1,R);
pushup(p);
}
inline void change(Re p,Re L,Re R,Re l,Re r){
if(tr[p].max<=1)return;
if(L==R){tr[p].max=tr[p].S=sqrt(tr[p].S);return;}
if(l<=mid)change(pl,L,mid,l,r);
if(r>mid)change(pr,mid+1,R,l,r);
pushup(p);
}
inline LL ask(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return tr[p].S;
LL ans=0;
if(l<=mid)ans+=ask(pl,L,mid,l,r);
if(r>mid)ans+=ask(pr,mid+1,R,l,r);
return ans;
}
}TR;
int main(){
in(n);
for(Re i=1;i<=n;++i)in(A[i]);
TR.build(1,1,n),in(T);
while(T--){
in(op),in(x),in(y);if(x>y)swap(x,y);
if(op)printf("%lld\n",TR.ask(1,1,n,x,y));
else TR.change(1,1,n,x,y);
}
}
#include<algorithm>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e4+3;
int n,x,y,T,op,A[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
struct QAQ{LL S,max,lmax,rmax;}tr[N<<2];
inline void pushup(QAQ &A,const QAQ &L,const QAQ &R){
A.S=L.S+R.S;
A.lmax=max(L.lmax,L.S+R.lmax);
A.rmax=max(R.rmax,R.S+L.rmax);
A.max=max(max(max(L.max,R.max),max(A.lmax,A.rmax)),L.rmax+R.lmax);
}
inline void change(Re p,Re L,Re R,Re x,Re v){
if(L==R){tr[p].S=tr[p].max=tr[p].lmax=tr[p].rmax=v;return;}
if(x<=mid)change(pl,L,mid,x,v);
else change(pr,mid+1,R,x,v);
pushup(tr[p],tr[pl],tr[pr]);
}
inline QAQ ask(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return tr[p];
if(r<=mid)return ask(pl,L,mid,l,r);
else if(l>mid)return ask(pr,mid+1,R,l,r);
else{QAQ ans;pushup(ans,ask(pl,L,mid,l,r),ask(pr,mid+1,R,l,r));return ans;}
}
}TR;
int main(){
in(n);
for(Re i=1;i<=n;++i)in(A[i]),TR.change(1,1,n,i,A[i]);
in(T);
while(T--){
in(op),in(x),in(y);
if(op)printf("%lld\n",TR.ask(1,1,n,x,y).max);
else TR.change(1,1,n,x,y);
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=6003;
int n,m,x,y,t,o,Ans,b[N],A[N],pt[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl (tr[p].lp)
#define pr (tr[p].rp)
#define mid ((L+R)>>1)
int O;
struct QAQ{int lp,rp,up,down;}tr[N*13*2];
inline void pushup(Re p){
tr[p].up=max(tr[pl].up,tr[pr].up);
tr[p].down=max(tr[pl].down,tr[pr].down);
}
inline void change1(Re &p,Re L,Re R,Re x,Re v){
if(!p)p=++O;
if(L==R){tr[p].up=max(tr[p].up,v);return;}
if(x<=mid)change1(pl,L,mid,x,v);
else change1(pr,mid+1,R,x,v);
pushup(p);
}
inline void change2(Re &p,Re L,Re R,Re x,Re v){
if(!p)p=++O;
if(L==R){tr[p].down=max(tr[p].down,v);return;}
if(x<=mid)change2(pl,L,mid,x,v);
else change2(pr,mid+1,R,x,v);
pushup(p);
}
inline int ask1(Re p,Re L,Re R,Re l,Re r){
if(!p)return 0;
if(l<=L&&R<=r)return tr[p].up;
Re ans=0;
if(l<=mid)ans=max(ans,ask1(pl,L,mid,l,r));
if(r>mid)ans=max(ans,ask1(pr,mid+1,R,l,r));
return ans;
}
inline int ask2(Re p,Re L,Re R,Re l,Re r){
if(!p)return 0;
if(l<=L&&R<=r)return tr[p].down;
Re ans=0;
if(l<=mid)ans=max(ans,ask2(pl,L,mid,l,r));
if(r>mid)ans=max(ans,ask2(pr,mid+1,R,l,r));
return ans;
}
inline int merge(Re p,Re q,Re L,Re R){
if(!p||!q)return p+q;
if(L==R){tr[p].up=max(tr[p].up,tr[q].up),tr[p].down=max(tr[p].down,tr[q].down);return p;}
Ans=max(Ans,max(tr[pl].up+tr[tr[q].rp].down,tr[pr].down+tr[tr[q].lp].up));
pl=merge(pl,tr[q].lp,L,mid);
pr=merge(pr,tr[q].rp,mid+1,R);
pushup(p);return p;
}
}TR;
inline void dfs(Re x,Re fa){
Re up=0,down=0;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa){
dfs(to,x);
Re tmp1=TR.ask1(pt[to],1,t,1,A[x]-1),tmp2=TR.ask2(pt[to],1,t,A[x]+1,t);
Ans=max(Ans,max(up+tmp2+1,down+tmp1+1));
up=max(up,tmp1),down=max(down,tmp2);
pt[x]=TR.merge(pt[x],pt[a[i].to],1,t);
}
TR.change1(pt[x],1,t,A[x],up+1),TR.change2(pt[x],1,t,A[x],down+1);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),m=n-1;
for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
sort(b+1,b+n+1),t=unique(b+1,b+n+1)-b;
for(Re i=1;i<=n;++i)A[i]=lower_bound(b+1,b+t+1,A[i])-b;
while(m--)in(x),in(y),add(x,y),add(y,x);
dfs(1,0),printf("%d\n",Ans);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=2e5+3;char opt[N];
int x,y,z,w,n,T,op,A[N],rk[N];
inline void in(int &x){
Re fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
int pt[N<<1];
struct Segment_Tree{
#define pl tr[p].lp
#define pr tr[p].rp
#define mid ((L+R)>>1)
int O;queue<int>Q;
struct QAQ{int S,lp,rp;}tr[N*200];
inline int New(){// 新建节点
if(Q.empty())return ++O;
Re tmp=Q.front();Q.pop();
return tmp;
}
inline void del(Re &p){pl=pr=0,Q.push(p),p=0;}// 删除节点(注意取地址,初始化为1)
inline void change(Re &p,Re L,Re R,Re w,Re v){
if(!p)p=New();tr[p].S+=v;
if(L==R){if(!tr[p].S)del(p);return;}
if(w<=mid)change(pl,L,mid,w,v);
else change(pr,mid+1,R,w,v);
if(!tr[p].S)del(p);
}
inline int ask(Re p,Re L,Re R,Re l,Re r){
if(!p)return 0;
if(l<=L&&R<=r)return tr[p].S;
Re ans=0;
if(l<=mid)ans+=ask(pl,L,mid,l,r);
if(r>mid)ans+=ask(pr,mid+1,R,l,r);
return ans;
}
}TR;
inline int ask(Re L,Re R,Re l,Re r){
Re ans=0;
for(Re i=R;i;i-=i&-i)ans+=TR.ask(pt[i],1,n,l,r);
for(Re i=L-1;i;i-=i&-i)ans-=TR.ask(pt[i],1,n,l,r);
return ans;
}
inline void add(Re x,Re w,Re v){
for(Re i=x;i<=n;i+=i&-i)TR.change(pt[i],1,n,w,v);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=1;i<=n;++i)in(x),rk[x]=i;
for(Re i=1;i<=n;++i)in(A[i]),A[i]=rk[A[i]],add(i,A[i],1);
while(T--){
in(op),in(x),in(y);
if(op>1)add(x,A[x],-1),add(y,A[y],-1),swap(A[x],A[y]),add(x,A[x],1),add(y,A[y],1);
else in(z),in(w),printf("%d\n",ask(z,w,x,y));
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int n,m,T,b[N<<1],A[N];char op[N];
struct QWQ{int x,y,k;}Q[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int t1,t2,pt[N],ptl[20],ptr[20];
struct President_Tree{
#define pl (tr[p].lp)
#define pr (tr[p].rp)
#define mid ((L+R)>>1)
int O;
struct QAQ{int S,lp,rp;}tr[(N<<1)*200];
inline void change(Re &p,Re L,Re R,Re x,Re v){
if(!p)p=++O;tr[p].S+=v;
if(L==R)return;
if(x<=mid)change(pl,L,mid,x,v);
else change(pr,mid+1,R,x,v);
}
inline int ask(Re p,Re L,Re R,Re K){
if(L==R)return L;
Re tmp=0;
for(Re i=1;i<=t1;++i)tmp-=tr[tr[ptl[i]].lp].S;
for(Re i=1;i<=t2;++i)tmp+=tr[tr[ptr[i]].lp].S;
if(K<=tmp){
for(Re i=1;i<=t1;++i)ptl[i]=tr[ptl[i]].lp;
for(Re i=1;i<=t2;++i)ptr[i]=tr[ptr[i]].lp;
return ask(pl,L,mid,K);
}
else{
for(Re i=1;i<=t1;++i)ptl[i]=tr[ptl[i]].rp;
for(Re i=1;i<=t2;++i)ptr[i]=tr[ptr[i]].rp;
return ask(pr,mid+1,R,K-tmp);
}
}
}SG;
struct BIT{
inline void add(Re x,Re v){
for(Re i=x;i<=n;i+=i&-i)SG.change(pt[i],1,m,A[x],v);
}
inline int ask(Re L,Re R,Re k){
t1=t2=0;
for(Re i=L-1;i;i-=i&-i)ptl[++t1]=pt[i];
for(Re i=R;i;i-=i&-i)ptr[++t2]=pt[i];
return SG.ask(1,1,m,k);
}
}TR;
int main(){
in(n),in(T),m=n;
for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
for(Re i=1;i<=T;++i){
scanf(" %c",&op[i]),in(Q[i].x),in(Q[i].y);
if(op[i]=='Q')in(Q[i].k);
else b[++m]=Q[i].y;
}
sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
for(Re i=1;i<=n;++i)A[i]=lower_bound(b+1,b+m+1,A[i])-b;
for(Re i=1;i<=T;++i)if(op[i]=='C')Q[i].y=lower_bound(b+1,b+m+1,Q[i].y)-b;
for(Re i=1;i<=n;++i)TR.add(i,1);
for(Re i=1;i<=T;++i){
if(op[i]=='Q')printf("%d\n",b[TR.ask(Q[i].x,Q[i].y,Q[i].k)]);
else TR.add(Q[i].x,-1),A[Q[i].x]=Q[i].y,TR.add(Q[i].x,1);
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2e4+3,M=5e4+3;
int n,m,x,y,z,T,op,X[N+M],Y[N+M],last[M];LL v[N+M],Ans[M];
inline void in(int &x){
Re fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct QWQ{int id,op;QWQ(Re ID=0,Re OP=0){id=ID,op=OP;}};
struct Link_Cut_Tree{
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
int size,Q[N+M];QWQ QQ[M*32];LL MST;
struct QAQ{int mx,fa,tag,ps[2];}tr[N+M];
inline void pushup(Re p){
tr[p].mx=p;
if(pl&&v[tr[pl].mx]>v[tr[p].mx])tr[p].mx=tr[pl].mx;
if(pr&&v[tr[pr].mx]>v[tr[p].mx])tr[p].mx=tr[pr].mx;
}
inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
inline void pushdown(Re p){
if(tr[p].tag){
if(pl)updata(pl);
if(pr)updata(pr);
tr[p].tag=0;
}
}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
inline void rotate(Re p){
Re fa=pf,fas=which(p);
Re pa=tr[fa].fa,pas=which(fa);
Re x=tr[p].ps[fas^1];
if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
connect(x,fa,fas),connect(fa,p,fas^1);
pushup(fa),pushup(p);
}
inline void splay(Re p){
Re x=p,t=0;Q[++t]=x;
while(nort(x))Q[++t]=x=tr[x].fa;
while(t)pushdown(Q[t--]);
for(Re fa;nort(p);rotate(p))
if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
}
inline void access(Re p){
for(Re son=0;p;son=p,p=pf)
splay(p),pr=son,pushup(p);
}
inline void makeroot(Re x){access(x),splay(x),updata(x);}
inline int findroot(Re p){
access(p),splay(p),pushdown(p);
while(pl)pushdown(p=pl);
return p;
}
inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
inline void link(Re x,Re y){makeroot(x),tr[x].fa=y;}
inline void cut(Re x,Re y){makeroot(x),access(y),splay(y),tr[x].fa=tr[y].ps[0]=0,pushup(y);}
inline void cut_(Re id){
makeroot(Y[id]),access(X[id]),splay(X[id]),tr[X[id]].ps[0]=tr[Y[id]].fa=tr[id].ps[0]=tr[id].fa=0,pushup(X[id]);
}
inline void link_(Re id){
makeroot(X[id]),makeroot(Y[id]),tr[X[id]].fa=tr[Y[id]].fa=id;
}
inline void MST_link(Re id){
Re x=X[id],y=Y[id];makeroot(x);
if(findroot(y)!=x)link(x,id),link(id,y),QQ[++size]=QWQ(id,0),MST+=v[id];
else{
Re mx=tr[y].mx;
if(v[id]<v[mx]){
// cut(X[mx],mx),cut(mx,Y[mx]),QQ[++size]=QWQ(mx,1);
cut_(mx),QQ[++size]=QWQ(mx,1);
link(x,id),link(id,y),QQ[++size]=QWQ(id,0);
// link_(id),QQ[++size]=QWQ(id,0);
MST+=v[id]-v[mx];
}
}
}
inline void back(Re to){
while(size>to){
QWQ a=QQ[size--];Re id=a.id;
if(a.op)link(id,Y[id]),link(X[id],id),MST+=v[id];
// else cut(id,Y[id]),cut(X[id],id),MST-=v[id];
// if(a.op)link_(id),MST+=v[id];
else cut_(id),MST-=v[id];
}
}
#undef pl
#undef pr
}LCT;
int o,head[M<<2];
struct QAQ{int id,next;LL v;}a[M*32];
inline void add(Re x,Re id,LL v){a[++o].id=id,a[o].v=v,a[o].next=head[x],head[x]=o;}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
inline void change(Re p,Re L,Re R,Re l,Re r,Re id,LL v){
if(l>r)return;
if(l<=L&&R<=r){add(p,id,v);return;}
if(l<=mid)change(pl,L,mid,l,r,id,v);
if(r>mid)change(pr,mid+1,R,l,r,id,v);
}
inline void dfs(Re p,Re L,Re R){
Re tmp=LCT.size;
for(Re i=head[p];i;i=a[i].next)v[a[i].id]=a[i].v,LCT.MST_link(a[i].id);
if(L==R)Ans[L]=LCT.MST;
else dfs(pl,L,mid),dfs(pr,mid+1,R);
LCT.back(tmp);
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
// freopen("my.txt","w",stdout);
in(n),in(m),in(T);
for(Re i=1;i<=m;++i)in(X[i+n]),in(Y[i+n]),in(x),v[i+n]=x,last[i]=1;
for(Re i=1;i<=T;++i){
in(x),in(y);
T1.change(1,1,T,last[x],i-1,x+n,v[x+n]);
last[x]=i,v[x+n]=y;
}
for(Re i=1;i<=m;++i)T1.change(1,1,T,last[i],T,i+n,v[i+n]);
T1.dfs(1,1,T);
for(Re i=1;i<=T;++i)printf("%lld\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<stack>
#include<map>
#define LL long long
#define Re register int
#define mp make_pair
using namespace std;
const int N=1e5+3,M=2e5+3;
int x,y,l,r,n,m,T,Ans[N];char ch[20];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Union{// 冰茶姬(并查集)
struct BK{int x,y,sizex,sizey;BK(Re X=0,Re S1=0,Re Y=0,Re S2=0){x=X,y=Y,sizex=S1,sizey=S2;}};
int fa[N<<1],size[N<<1];stack<BK>Q;
inline int find(Re x){return fa[x]==x?x:find(fa[x]);}
inline void merge(Re x,Re y){// 启发式合并
x=find(x),y=find(y);
if(x==y)return;
if(size[x]>size[y])swap(x,y);
Q.push(BK(x,size[x],y,size[y]));
fa[x]=y,size[y]+=size[x];
}
inline void back(Re to){// 撤销操作
while(int(Q.size())>to){
BK a=Q.top();Q.pop();
fa[a.x]=a.x,size[a.x]=a.sizex;
fa[a.y]=a.y,size[a.y]=a.sizey;
}
}
}TF;
int o,head[N<<2];
struct QAQ{int x,y,next;}a[M*20];
inline void add(Re x,Re y1,Re y2){a[++o].x=y1,a[o].y=y2,a[o].next=head[x],head[x]=o;}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re y){
if(l>r)return;
if(l<=L&&R<=r){add(p,x,y);return;}
if(l<=mid)change(pl,L,mid,l,r,x,y);
if(r>mid)change(pr,mid+1,R,l,r,x,y);
}
inline void dfs(Re p,Re L,Re R){
Re tmp=TF.Q.size();
for(Re i=head[p];i;i=a[i].next){
if(TF.find(a[i].x)==TF.find(a[i].y)){
for(Re j=L;j<=R;++j)Ans[j]=1;
TF.back(tmp);return;
}
TF.merge(a[i].x,a[i].y+n),TF.merge(a[i].x+n,a[i].y);
}
if(L<R)dfs(pl,L,mid),dfs(pr,mid+1,R);
TF.back(tmp);
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m),in(T);
for(Re i=1;i<=(n<<1);++i)TF.fa[i]=i,TF.size[i]=1;
for(Re i=1;i<=m;++i)in(x),in(y),in(l),in(r),T1.change(1,1,T,l+1,r+1-1,x,y);
T1.dfs(1,1,T);
for(Re i=1;i<=T;++i)puts(Ans[i]?"No":"Yes");
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<stack>
#include<map>
#define LL long long
#define Re register int
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N=1e4+3,M=2e5+3;
int x,y,n,T,Ans[M];char ch[20];
map<pair<int,int>,int>last;
struct Query{int x,y,op;}Q[M];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Union{// 冰茶姬(并查集)
struct BK{int x,y,sizex,sizey;BK(Re X=0,Re S1=0,Re Y=0,Re S2=0){x=X,y=Y,sizex=S1,sizey=S2;}};
int fa[N],size[N];stack<BK>Q;
inline int find(Re x){return fa[x]==x?x:find(fa[x]);}
inline void merge(Re x,Re y){// 启发式合并
x=find(x),y=find(y);
if(size[x]>size[y])swap(x,y);
Q.push(BK(x,size[x],y,size[y]));
fa[x]=y,size[y]+=size[x];
}
inline void back(Re to){// 撤销操作
while(Q.size()>to){
BK a=Q.top();Q.pop();
fa[a.x]=a.x,size[a.x]=a.sizex;
fa[a.y]=a.y,size[a.y]=a.sizey;
}
}
}TF;
int o,head[M<<2];
struct QAQ{int x,y,next;}a[M*20];
inline void add(Re x,Re y1,Re y2){a[++o].x=y1,a[o].y=y2,a[o].next=head[x],head[x]=o;}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid (L+R>>1)
inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re y){
if(l<=L&&R<=r){add(p,x,y);return;}
if(l<=mid)change(pl,L,mid,l,r,x,y);
if(r>mid)change(pr,mid+1,R,l,r,x,y);
}
inline void dfs(Re p,Re L,Re R){
Re tmp=TF.Q.size();
for(Re i=head[p];i;i=a[i].next)TF.merge(a[i].x,a[i].y);
if(L==R){if(Q[L].op)Ans[L]=(TF.find(Q[L].x)==TF.find(Q[L].y));}
else dfs(pl,L,mid),dfs(pr,mid+1,R);
TF.back(tmp);
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=1;i<=n;++i)TF.fa[i]=i,TF.size[i]=1;
for(Re i=1;i<=T;++i){
scanf("%s",ch),in(x),in(y);if(x>y)swap(x,y);
if(ch[0]=='Q')Q[i].op=1,Q[i].x=x,Q[i].y=y;
else if(ch[0]=='C')last[mp(x,y)]=i;
else T1.change(1,1,T,last[mp(x,y)],i,x,y),last.erase(mp(x,y));
}
for(map<pair<int,int>,int>::iterator it=last.begin();it!=last.end();++it)
T1.change(1,1,T,it->second,T,it->first.first,it->first.second);
T1.dfs(1,1,T);
for(Re i=1;i<=T;++i)if(Q[i].op)puts(Ans[i]?"Yes":"No");
}
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<stack>
#define LL long long
#define Re register int
#define Int bitset<M>
using namespace std;
const int N=550+5,M=1000+5;
int n,m,x,y,o,O,T,logN,X[N],Y[N],fa[N],last[N],head[N];Int z,Z[N],dis[N],Ans[M];char op[20];
struct QAQ{int to,next;Int w;}a[N<<1];
inline void add(Re x,Re y,Int z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}
inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline int getlen(Int &x){Re n=1000;while(n>=1&&!x[n])--n;return n;}
inline void print(Int &x){for(Re i=getlen(x);i>=0;--i)putchar(x[i]+'0');puts("");}
inline void in(Int &x){cin>>x,logN=max(logN,getlen(x));}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Line_JI{
Int p[M];bool pp[M];stack<int>Q;
inline void insert(Int x){
for(Re i=logN;i>=0;--i)
if(x[i]){
if(!pp[i]){Q.push(i),p[i]=x,pp[i]=1;break;}
x^=p[i];
}
}
inline Int ask(){
Int ans;ans.reset();
for(Re i=logN;i>=0;--i)if(pp[i]&&(!ans[i]))ans^=p[i];
return ans;
}
inline void back(Re to){
while(Q.size()>to)x=Q.top(),Q.pop(),p[x].reset(),pp[x]=0;
}
}JI;
struct Segment_Tree{
int o,head[M<<2];
struct QAQ{int x,y,next;Int w;}a[(N+M)*10];
inline void add(Re t,Re x,Re y,Int &z){a[++o].x=x,a[o].y=y,a[o].w=z,a[o].next=head[t],head[t]=o;}
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re y,Int &z){
if(l<=L&&R<=r){add(p,x,y,z);return;}
if(l<=mid)change(pl,L,mid,l,r,x,y,z);
if(r>mid)change(pr,mid+1,R,l,r,x,y,z);
}
inline void dfs(Re p,Re L,Re R){
Re tmp=JI.Q.size();
for(Re i=head[p];i;i=a[i].next)JI.insert(dis[a[i].x]^dis[a[i].y]^a[i].w);
if(L==R)Ans[L]=JI.ask();// 这里还没做back撤销操作,不能return!!!
else dfs(pl,L,mid),dfs(pr,mid+1,R);
JI.back(tmp);
}
}TR;
inline void dfs(Re x,Re fa,Re w){
dis[x]=dis[fa]^a[w].w;
for(Re i=head[x];i;i=a[i].next)
if(a[i].to!=fa)dfs(a[i].to,x,i);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m),in(T),++T;
for(Re i=1;i<=n;++i)fa[i]=i;
while(m--){
in(x),in(y),in(z);
if(find(x)!=find(y))add(x,y,z),add(y,x,z),fa[find(x)]=find(y);
else TR.change(1,1,T,1,T,x,y,z);
}
for(Re i=2;i<=T;++i){
scanf("%s",op);
if(op[0]=='A')last[++O]=i,in(X[O]),in(Y[O]),in(Z[O]);
else if(op[1]=='h'){
in(x),in(z);
TR.change(1,1,T,last[x],i-1,X[x],Y[x],Z[x]);
last[x]=i,Z[x]=z;
}
else in(x),TR.change(1,1,T,last[x],i-1,X[x],Y[x],Z[x]),last[x]=0;
}
for(Re i=1;i<=O;++i)if(last[i])TR.change(1,1,T,last[i],T,X[i],Y[i],Z[i]);
dfs(1,0,0),TR.dfs(1,1,T);
for(Re i=1;i<=T;++i)print(Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#define LL long long
#define Re register int
#define IT set<QAQ>::iterator
using namespace std;
const int N=1e5+3;
int n,m,l,r,T,op,A[N],tmp[N],cnt[N],Ans[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct QAQ{
int l,r;mutable int pt,op;
QAQ(Re L=0,Re R=0,Re OP=0,Re PT=0){l=L,r=R,op=OP,pt=PT;};
inline bool operator<(const QAQ &O)const{return l<O.l;}
};
set<QAQ>s;
struct Segment_Tree{
#define pl tr[p].lp
#define pr tr[p].rp
#define mid ((L+R)>>1)
int O;
struct QAQ{int S,lp,rp;}tr[N*60];
inline void pushup(Re p){tr[p].S=tr[pl].S+tr[pr].S;}
inline void change(Re &p,Re L,Re R,Re x){
p=++O;
if(L==R){tr[p].S=1;return;}
if(x<=mid)change(pl,L,mid,x);
else change(pr,mid+1,R,x);
pushup(p);
}
inline int merge(Re p,Re q,Re L,Re R){
if(!p||!q)return p+q;
if(L==R){tr[p].S+=tr[q].S;return p;}
pl=merge(pl,tr[q].lp,L,mid);
pr=merge(pr,tr[q].rp,mid+1,R);
pushup(p);return p;
}
inline void split1(Re &p,Re q,Re L,Re R,Re k){// 取q中的前k个,分到新节点p
tr[p=++O].S=tr[q].S-k,tr[q].S=k;
if(L==R)return;
Re tmp=tr[tr[q].lp].S;
if(k>tmp)split1(pr,tr[q].rp,mid+1,R,k-tmp);// q左子树全部分给p,只剩右子树
else pr=tr[q].rp,tr[q].rp=0;// 右子树全部分给p
if(k<tmp)split1(pl,tr[q].lp,L,mid,k);// q的右子树全部分给p,只剩左子树
}
inline void split2(Re &p,Re q,Re L,Re R,Re k){// 取q中的后k个,分到新节点p
tr[p=++O].S=tr[q].S-k,tr[q].S=k;
if(L==R)return;
Re tmp=tr[tr[q].rp].S;
if(k>tmp)split2(pl,tr[q].lp,L,mid,k-tmp);// q的右子树全部分给p,只剩左子树
else pl=tr[q].lp,tr[q].lp=0;// 左子树全部分给p
if(k<tmp)split2(pr,tr[q].rp,mid+1,R,k);// q左子树全部分给p,只剩右子树
}
inline void dfs(Re p,Re L,Re R){
if(!p)return;
if(L==R){cnt[tmp[++tmp[0]]=L]=tr[p].S;return;}
dfs(pl,L,mid),dfs(pr,mid+1,R);
}
}T1;
inline IT split(Re w){
IT it=s.lower_bound(QAQ(w));
if(it!=s.end()&&it->l==w)return it;
--it;
Re L=it->l,R=it->r,op=it->op,pt=it->pt,ptt=0;
s.erase(it);
if(op)T1.split1(ptt,pt,1,m,w-1-L+1);
else T1.split2(ptt,pt,1,m,w-1-L+1);
s.insert(QAQ(L,w-1,op,pt));
return s.insert(QAQ(w,R,op,ptt)).first;
}
inline void assign(Re l,Re r,Re op){
if(l==r)return;
IT itr=split(r+1),itl=split(l),it=itl;
Re pt=0;
while(it!=itr)pt=T1.merge(pt,it->pt,1,m),it->pt=0,++it;
s.erase(itl,itr),s.insert(QAQ(l,r,op,pt));
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),m=n;
for(Re i=1;i<=n;++i)in(A[i]);
s.insert(QAQ(n+1,n+1));
for(Re i=1;i<=n;++i){
QAQ tmp(i,i,0,0);T1.change(tmp.pt,1,m,A[i]),s.insert(tmp);
}
while(T--)in(op),in(l),in(r),op^=1,assign(l,r,op);
IT itl=s.lower_bound(QAQ(1)),itr=s.lower_bound(QAQ(n+1));
while(itl!=itr){
tmp[0]=0,T1.dfs(itl->pt,1,m);
if(itl->op)for(Re i=1;i<=tmp[0];++i)
for(Re j=1;j<=cnt[tmp[i]];++j)
Ans[++Ans[0]]=tmp[i];
else for(Re i=tmp[0];i>=1;--i)
for(Re j=1;j<=cnt[tmp[i]];++j)
Ans[++Ans[0]]=tmp[i];
++itl;
}
in(op),printf("%d\n",Ans[op]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2e5+3;
int n,m,x,y,p,T,op,A[N],pt[N];LL K;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl tr[p].lp
#define pr tr[p].rp
#define mid ((L+R)>>1)
int O;
struct QAQ{int lp,rp;LL S;}tr[N*20];
inline void pushup(Re p){tr[p].S=tr[pl].S+tr[pr].S;}
inline void build(Re &p,Re L,Re R){
p=++O;
if(L==R){tr[p].S=A[L];return;}
build(pl,L,mid),build(pr,mid+1,R);
pushup(p);
}
inline void change(Re &p,Re L,Re R,Re x,Re v){
if(!p)p=++O;
if(L==R){tr[p].S+=v;return;}
if(x<=mid)change(pl,L,mid,x,v);
else change(pr,mid+1,R,x,v);
pushup(p);
}
inline LL ask(Re p,Re L,Re R,Re l,Re r){
if(!p)return 0;
if(l<=L&&R<=r)return tr[p].S;
LL ans=0;
if(l<=mid)ans+=ask(pl,L,mid,l,r);
if(r>mid)ans+=ask(pr,mid+1,R,l,r);
return ans;
}
inline int ask(Re p,Re L,Re R,LL k){
if(!p||k>tr[p].S)return -1;
if(L==R)return L;
LL tmp=tr[pl].S;
if(tmp>=k)return ask(pl,L,mid,k);
else return ask(pr,mid+1,R,k-tmp);
}
inline int merge(Re p,Re q,Re L,Re R){
if(!p||!q)return p+q;
if(L==R){tr[p].S+=tr[q].S;return p;}
pl=merge(pl,tr[q].lp,L,mid);
pr=merge(pr,tr[q].rp,mid+1,R);
pushup(p);return p;
}
inline void split(Re &p,Re &q,Re L,Re R,Re l,Re r){
if(!q)return;
if(l<=L&&R<=r){p=q,q=0;return;}
p=++O;
if(l<=mid)split(pl,tr[q].lp,L,mid,l,r);
if(r>mid)split(pr,tr[q].rp,mid+1,R,l,r);
pushup(p),pushup(q);
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(m),in(T);
for(Re i=1;i<=m;++i)in(A[i]);
T1.build(pt[n=1],1,m);
while(T--){
in(op),in(p);
if(op<1)in(x),in(y),T1.split(pt[++n],pt[p],1,m,x,y);
else if(op<2)in(x),pt[p]=T1.merge(pt[p],pt[x],1,m),pt[x]=0;
else if(op<3)in(x),in(y),T1.change(pt[p],1,m,y,x);
else if(op<4)in(x),in(y),printf("%lld\n",T1.ask(pt[p],1,m,x,y));
else scanf("%lld",&K),printf("%d\n",T1.ask(pt[p],1,m,K));
}
}
#include<algorithm>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,logN=17;
int n,m,x,o,T,op,b[N],A[N],Ans[N],head[N];
struct QAQ{int to,next;}a[N];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int pt[N];
struct Segment_Tree{
#define pl (tr[p].lp)
#define pr (tr[p].rp)
#define mid ((L+R)>>1)
int O;
struct QAQ{int lp,rp,S;}tr[N*(logN+1)];
inline void pushup(Re p){tr[p].S=tr[pl].S+tr[pr].S;}
inline void change(Re &p,Re L,Re R,Re x){
p=++O,++tr[p].S;
if(L==R)return;
if(x<=mid)change(pl,L,mid,x);
else change(pr,mid+1,R,x);
}
inline int merge(Re p,Re q,Re L,Re R){
if(!p||!q)return p+q;
if(L==R){tr[p].S+=tr[q].S;return p;}
pl=merge(pl,tr[q].lp,L,mid);
pr=merge(pr,tr[q].rp,mid+1,R);
pushup(p);return p;
}
inline int ask(Re &p,Re L,Re R,Re l,Re r){
if(!p)return 0;
if(l<=L&&R<=r)return tr[p].S;
Re ans=0;
if(l<=mid)ans+=ask(pl,L,mid,l,r);
if(r>mid)ans+=ask(pr,mid+1,R,l,r);
return ans;
}
}TR;
inline void dfs(Re x,Re fa){
TR.change(pt[x],1,m,A[x]);
for(Re i=head[x],to;i;i=a[i].next)
dfs(to=a[i].to,x),pt[x]=TR.merge(pt[x],pt[to],1,m);
if(A[x]<m)Ans[x]=TR.ask(pt[x],1,m,A[x]+1,m);
}
int main(){
in(n);
for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
sort(b+1,b+n+1),m=unique(b+1,b+n+1)-b-1;
for(Re i=1;i<=n;++i)A[i]=lower_bound(b+1,b+m+1,A[i])-b;
for(Re i=2;i<=n;++i)in(x),add(x,i);
dfs(1,0);
for(Re i=1;i<=n;++i)printf("%d\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,M=5e4;
int n,x,T;LD b[N],k[N];char s[20];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline LD y(Re id,Re x){return k[id]*x+b[id];}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
int tr[N<<2];
inline void change(Re p,Re L,Re R,Re id){
if(y(id,L)>y(tr[p],L)&&y(id,R)>y(tr[p],R)){tr[p]=id;return;}
if(y(id,L)<=y(tr[p],L)&&y(id,R)<=y(tr[p],R))return;
// if(L==R){if(y(id,L)>y(tr[p],L))tr[p]=id;return;}
if(k[tr[p]]<k[id]){
if(y(id,mid+1)>y(tr[p],mid+1))change(pl,L,mid,tr[p]),tr[p]=id;
else change(pr,mid+1,R,id);
}
else{
if(y(id,mid)>y(tr[p],mid))change(pr,mid+1,R,tr[p]),tr[p]=id;
else change(pl,L,mid,id);
}
}
inline LD ask(Re p,Re L,Re R,Re x){
if(L==R)return y(tr[p],x);
LD ans=y(tr[p],x);
if(x<=mid)return max(ans,ask(pl,L,mid,x));
else return max(ans,ask(pr,mid+1,R,x));
}
}TR;
int main(){
// freopen("123.txt","r",stdin);
in(T);
while(T--){
scanf("%s",s);
if(s[0]=='P')++n,scanf("%lf%lf",&b[n],&k[n]),TR.change(1,1,M,n);
else in(x),printf("%d\n",(int)(TR.ask(1,1,M,x-1)/100));
}
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int x,y,z,n,m,T,t,fu,cnt,tl,tr,a[N],b[N],pt[N],C[N],opt[N],ptl[20],ptr[20];
struct QAQ{int g,lp,rp;}tree[N*250];
struct O_O{int l,r,k;}Q[N];
struct T_T{int i,x;}c[N];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline int ask_kth(Re L,Re R,Re k){
if(L==R)return b[R];
Re tmp=0;
F(i,1,tl)tmp-=tree[tree[ptl[i]].lp].g;
F(i,1,tr)tmp+=tree[tree[ptr[i]].lp].g;
if(tmp>=k){
F(i,1,tl)ptl[i]=tree[ptl[i]].lp;
F(i,1,tr)ptr[i]=tree[ptr[i]].lp;
return ask_kth(L,mid,k);
}
else{
F(i,1,tl)ptl[i]=tree[ptl[i]].rp;
F(i,1,tr)ptr[i]=tree[ptr[i]].rp;
return ask_kth(mid+1,R,k-tmp);
}
}
inline int ask_kth_pre(Re L,Re R,Re k){
tl=tr=0;
for(Re i=L-1;i;i-=i&-i)ptl[++tl]=pt[i];
for(Re i=R;i;i-=i&-i)ptr[++tr]=pt[i];
return ask_kth(1,m,k);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
if(!p)p=++cnt;tree[p].g+=v;
if(L==R)return;
if(w<=mid)add(pl,L,mid,w,v);
else add(pr,mid+1,R,w,v);
}
inline void add_pre(Re x,Re v){
Re w=lo(a[x]);
for(Re i=x;i<=n;i+=i&-i)add(pt[i],1,m,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
if(L==R)return tree[p].g;
if(x<=mid)return ask_level(pl,L,mid,x);
else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
inline int ask_level_pre(Re L,Re R,Re w){
Re ans=0;
for(Re i=R;i;i-=i&-i)ans+=ask_level(pt[i],1,m,w);
for(Re i=L-1;i;i-=i&-i)ans-=ask_level(pt[i],1,m,w);
return ans;
}
int main(){
// printf("%lf\n",(sizeof(tree))/1024.0/1024.0);
// printf("%lf\n",(sizeof(tree)+sizeof(Q)+sizeof(c)+sizeof(a)+sizeof(b)+sizeof(pt)+sizeof(C))/1024.0/1024.0);
in(n),in(T),m=n;
F(i,1,n)in(a[i]),b[i]=a[i];
F(i,1,T){
in(opt[i]);
if(opt[i]==3)in(c[i].i),in(c[i].x),b[++m]=c[i].x;
else{
in(Q[i].l),in(Q[i].r),in(Q[i].k);
if(opt[i]!=2)b[++m]=Q[i].k;
}
}
sort(b+1,b+m+1);
m=unique(b+1,b+m+1)-b-1;
F(i,1,n)add_pre(i,1);
F(i,1,T){
if(opt[i]==1)
Q[i].k=lo(Q[i].k),
printf("%d\n",ask_level_pre(Q[i].l,Q[i].r,Q[i].k-1)+1);
if(opt[i]==2)
printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,Q[i].k));
if(opt[i]==3)
add_pre(c[i].i,-1),a[c[i].i]=c[i].x,add_pre(c[i].i,1);
if(opt[i]==4){
}
if(opt[i]==5){
}
}
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int x,y,z,n,m,T,t,fu,cnt,tl,tr,a[N],b[N],pt[N],C[N],opt[N],ptl[20],ptr[20];
struct QAQ{int g,lp,rp;}tree[N*250];
struct O_O{int l,r,k;}Q[N];
struct T_T{int i,x;}c[N];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline int ask_kth(Re L,Re R,Re k){
if(L==R)return b[R];
Re tmp=0;
F(i,1,tl)tmp-=tree[tree[ptl[i]].lp].g;
F(i,1,tr)tmp+=tree[tree[ptr[i]].lp].g;
if(tmp>=k){
F(i,1,tl)ptl[i]=tree[ptl[i]].lp;
F(i,1,tr)ptr[i]=tree[ptr[i]].lp;
return ask_kth(L,mid,k);
}
else{
F(i,1,tl)ptl[i]=tree[ptl[i]].rp;
F(i,1,tr)ptr[i]=tree[ptr[i]].rp;
return ask_kth(mid+1,R,k-tmp);
}
}
inline int ask_kth_pre(Re L,Re R,Re k){
tl=tr=0;
for(Re i=L-1;i;i-=i&-i)ptl[++tl]=pt[i];
for(Re i=R;i;i-=i&-i)ptr[++tr]=pt[i];
return ask_kth(1,m,k);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
if(!p)p=++cnt;tree[p].g+=v;
if(L==R)return;
if(w<=mid)add(pl,L,mid,w,v);
else add(pr,mid+1,R,w,v);
}
inline void add_pre(Re x,Re v){
Re w=lo(a[x]);
for(Re i=x;i<=n;i+=i&-i)add(pt[i],1,m,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
if(L==R)return tree[p].g;
if(x<=mid)return ask_level(pl,L,mid,x);
else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
inline int ask_level_pre(Re L,Re R,Re w){
Re ans=0;
for(Re i=R;i;i-=i&-i)ans+=ask_level(pt[i],1,m,w);
for(Re i=L-1;i;i-=i&-i)ans-=ask_level(pt[i],1,m,w);
return ans;
}
int main(){
in(n),in(T),m=n;
F(i,1,n)in(a[i]),b[i]=a[i];
F(i,1,T){
in(opt[i]);
if(opt[i]==3)in(c[i].i),in(c[i].x),b[++m]=c[i].x;
else{
in(Q[i].l),in(Q[i].r),in(Q[i].k);
if(opt[i]!=2)b[++m]=Q[i].k;
}
}
sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
F(i,1,n)add_pre(i,1);
F(i,1,T){
if(opt[i]==1)Q[i].k=lo(Q[i].k),printf("%d\n",ask_level_pre(Q[i].l,Q[i].r,Q[i].k-1)+1);
if(opt[i]==2)printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,Q[i].k));
if(opt[i]==3)add_pre(c[i].i,-1),a[c[i].i]=c[i].x,add_pre(c[i].i,1);
if(opt[i]==4){
Re level=ask_level_pre(Q[i].l,Q[i].r,lo(Q[i].k)-1);
if(!level)printf("%d\n",-inf);
else printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,level));
}
if(opt[i]==5){
Re level=ask_level_pre(Q[i].l,Q[i].r,lo(Q[i].k));
if(level==Q[i].r-Q[i].l+1)printf("%d\n",inf);
else printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,level+1));
}
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=3e5+3,P=998244353;
int n,m,x,ans,inv1e4,f[N],b[N],p[N],A[N],fa[N],ch[N][3];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline int mi(Re x,Re k){
Re s=1;
while(k){
if(k&1)s=(LL)s*x%P;
x=(LL)x*x%P,k>>=1;
}
return s;
}
inline int inv(Re x){return mi(x,P-2);}
int pt[N];
struct Segment_Tree{
#define pl tr[p].lp
#define pr tr[p].rp
#define mid ((L+R)>>1)
int O;
struct QAQ{int S,lp,rp,mul;}tr[N*19];
inline void pushup(Re p){
tr[p].S=(tr[pl].S+tr[pr].S)%P;
}
inline void updata(Re p,Re v){
tr[p].S=(LL)tr[p].S*v%P,tr[p].mul=(LL)tr[p].mul*v%P;
}
inline void pushdown(Re p){
if(tr[p].mul!=1)updata(pl,tr[p].mul),updata(pr,tr[p].mul),tr[p].mul=1;
}
inline void change(Re &p,Re L,Re R,Re x,Re v){
if(!p)p=++O;tr[p].mul=1;
if(L==R){tr[p].S=v;return;}
pushdown(p);
if(x<=mid)change(pl,L,mid,x,v);
else change(pr,mid+1,R,x,v);
pushup(p);
}
inline int merge(Re p,Re q,Re pv,Re qv,Re v){
// printf("pv=%d, qv=%d, v=%d\n",pv,qv,v);
if(!p&&!q)return 0;
if(!p){updata(q,qv);return q;}
if(!q){updata(p,pv);return p;}
pushdown(p),pushdown(q);
Re plS=tr[pl].S,prS=tr[pr].S,qlS=tr[tr[q].lp].S,qrS=tr[tr[q].rp].S;
// printf("p:%d,%d q:%d,%d\n",tr[pl].S,tr[pr].S,tr[tr[q].lp].S,tr[tr[q].rp].S);
pl=merge(pl,tr[q].lp,(pv+(1-v+P)%P*1ll*qrS%P)%P,(qv+(1-v+P)%P*1ll*prS%P)%P,v);
pr=merge(pr,tr[q].rp,(pv+(LL)v*qlS%P)%P,(qv+(LL)v*plS%P)%P,v);
pushup(p);
return p;
}
inline void dfs_(Re p,Re L,Re R){
if(!p)return;
if(L==R){f[L]=tr[p].S;return;}
pushdown(p),dfs_(pl,L,mid),dfs_(pr,mid+1,R);
}
inline int ask(Re p,Re L,Re R,Re x){
if(!p)return 0;
if(L==R)return tr[p].S;
pushdown(p);
if(x<=mid)return ask(pl,L,mid,x);
else return ask(pr,mid+1,R,x);
}
}T1;
inline void dfs(Re x){
if(!ch[x][0])T1.change(pt[x],1,m,A[x],1);
else{
// printf("x=%d:\n",x);
// for(Re i=1;i<=m;++i)printf("%d ",T1.ask(pt[x],1,m,i));puts("");
dfs(ch[x][1]);
if(ch[x][0]<2)pt[x]=pt[ch[x][1]];
else dfs(ch[x][2]),pt[x]=T1.merge(pt[ch[x][1]],pt[ch[x][2]],0,0,p[x]);
// printf("x=%d:\n",x);
// for(Re i=1;i<=m;++i)printf("%d ",T1.ask(pt[x],1,m,i));puts("");
}
}
int main(){
// freopen("123.txt","r",stdin);
in(n),inv1e4=inv(10000);
for(Re i=1;i<=n;++i)in(fa[i]),ch[fa[i]][++ch[fa[i]][0]]=i;
for(Re i=1;i<=n;++i)
if(ch[i][0])in(p[i]),p[i]=(LL)p[i]*inv1e4%P;
else in(x),b[++m]=A[i]=x;
sort(b+1,b+m+1);
for(Re i=1;i<=n;++i)if(!ch[i][0])A[i]=lower_bound(b+1,b+m+1,A[i])-b;
// for(Re i=1;i<=n;++i)if(!ch[i][0])printf("%d: %d\n",i,A[i]);
dfs(1),T1.dfs_(1,1,m);
// for(Re i=1;i<=m;++i)printf("%d ",f[i]);puts("");
for(Re i=1;i<=m;++i)(ans+=(LL)i*b[i]%P*f[i]%P*f[i]%P)%=P;
printf("%d\n",ans);
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int m,T,t,fu,cnt,root,a[N],b[N],Q[N],opt[N];
struct QAQ{int g,lp,rp;}tree[N<<1];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline int ask_kth(Re p,Re L,Re R,Re k){
if(L==R)return b[R];
Re tmp=tree[pl].g;
if(tmp>=k)return ask_kth(pl,L,mid,k);
else return ask_kth(pr,mid+1,R,k-tmp);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
if(!p)p=++cnt;tree[p].g+=v;
if(L==R)return;
if(w<=mid)add(pl,L,mid,w,v);
else add(pr,mid+1,R,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
if(!x)return 0;
if(L==R)return tree[p].g;
if(x<=mid)return ask_level(pl,L,mid,x);
else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
int main(){
in(T);
F(i,1,T){
in(opt[i]),in(Q[i]);
if(opt[i]!=4)b[++m]=Q[i];
}
sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
F(i,1,T){
if(opt[i]==1)add(root,1,m,lo(Q[i]),1);
if(opt[i]==2)add(root,1,m,lo(Q[i]),-1);
if(opt[i]==3)printf("%d\n",ask_level(root,1,m,lo(Q[i])-1)+1);
if(opt[i]==4)printf("%d\n",ask_kth(root,1,m,Q[i]));
if(opt[i]==5){
Re level=ask_level(root,1,m,lo(Q[i])-1);
printf("%d\n",ask_kth(root,1,m,level));
}
if(opt[i]==6){
Re level=ask_level(root,1,m,lo(Q[i]));
printf("%d\n",ask_kth(root,1,m,level+1));
}
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<stack>
#include<map>
#define LL long long
#define Re register int
#define mp make_pair
using namespace std;
const int N=2e5+3,logN=30;
int x,y,n,m,T,op,X[N],Y[N],OP[N];LL Ans[N];map<pair<int,int>,int>last,z;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Union{// 冰茶姬(并查集)
struct BK{int x,y,dx,dy,sx,sy;BK(Re X=0,Re d1=0,Re S1=0,Re Y=0,Re d2=0,Re S2=0){x=X,y=Y,sx=S1,sy=S2,dx=d1,dy=d2;}};
int fa[N],dis[N],size[N];stack<BK>Q;
inline int find(Re x){return fa[x]==x?x:find(fa[x]);}
inline int Dis(Re x){return fa[x]==x?0:dis[x]^Dis(fa[x]);}
inline void merge(Re x,Re y,Re w){// 启发式合并
if(size[x]>size[y])swap(x,y);
Q.push(BK(x,dis[x],size[x],y,dis[y],size[y]));
fa[x]=y,dis[x]=w,size[y]+=size[x];
}
inline void back(Re to){// 撤销操作
while(int(Q.size())>to){
BK a=Q.top();Re x=a.x,y=a.y;Q.pop();
fa[x]=x,dis[x]=a.dx,size[x]=a.sx;
fa[y]=y,dis[y]=a.dy,size[y]=a.sy;
}
}
}TF;
struct Line_JI{
int p[31];stack<int>Q;
inline void insert(Re x){
for(Re i=logN;i>=0;--i)
if((x>>i)&1){
if(!p[i]){p[i]=x,Q.push(i);break;}
x^=p[i];
}
}
inline int ask(Re x){for(Re i=logN;i>=0;--i)if(p[i])x=min(x,x^p[i]);return x;}
inline void back(Re to){
while(int(Q.size())>to)p[Q.top()]=0,Q.pop();
}
}JI;
int o,head[N<<2];
struct QAQ{int x,y,w,next;}a[N*50];
inline void add(Re x,Re y1,Re y2,Re w){a[++o].w=w,a[o].x=y1,a[o].y=y2,a[o].next=head[x],head[x]=o;}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re y,Re v){
if(l>r)return;
if(l<=L&&R<=r){add(p,x,y,v);return;}
if(l<=mid)change(pl,L,mid,l,r,x,y,v);
if(r>mid)change(pr,mid+1,R,l,r,x,y,v);
}
inline void dfs(Re p,Re L,Re R){
Re tmp1=TF.Q.size(),tmp2=JI.Q.size();
for(Re i=head[p];i;i=a[i].next){
Re x=TF.find(a[i].x),y=TF.find(a[i].y),w=TF.Dis(a[i].x)^TF.Dis(a[i].y)^a[i].w;
if(x!=y)TF.merge(x,y,w);
else JI.insert(w);
}
if(L==R){if(OP[L])Ans[L]=JI.ask(TF.Dis(X[L])^TF.Dis(Y[L]));}
else dfs(pl,L,mid),dfs(pr,mid+1,R);
TF.back(tmp1),JI.back(tmp2);
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m);
for(Re i=1;i<=n;++i)TF.fa[i]=i,TF.size[i]=1;
for(Re i=1;i<=m;++i){
in(x),in(y);if(x>y)swap(x,y);
in(z[mp(x,y)]),last[mp(x,y)]=1;
}
in(T);
for(Re i=1;i<=T;++i){
in(op),in(x),in(y);if(x>y)swap(x,y);
if(op<2)in(z[mp(x,y)]),last[mp(x,y)]=i;
else if(op<3)T1.change(1,1,T,last[mp(x,y)],i-1,x,y,z[mp(x,y)]),last.erase(last.find(mp(x,y)));
else OP[i]=1,X[i]=x,Y[i]=y;
}
for(map<pair<int,int>,int>::iterator it=last.begin();it!=last.end();++it)
T1.change(1,1,T,it->second,T,it->first.first,it->first.second,z[it->first]);
T1.dfs(1,1,T);
for(Re i=1;i<=T;++i)if(OP[i])printf("%lld\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,logN=18;
int n,x,y,z,w,op,m1,m2,T,A[N],t1[N],t2[N],Ans[N];
struct Change{int i,v,t;inline bool operator<(const Change &O)const{return i<O.i;}}C[N],tmp[N];
struct Query{int x,l,r,id;}Q[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int pt[N];
struct Trie{
int O,cnt[N*(logN+2)],tr[N*(logN+2)][2];
inline void insert(Re p,Re q,Re o,Re x){
if(o<0)return;Re i=(x>>o)&1;
tr[p][i]=++O,tr[p][i^1]=tr[q][i^1];
cnt[tr[p][i]]=cnt[tr[q][i]]+1;
insert(tr[p][i],tr[q][i],o-1,x);
}
inline int ask(Re p,Re q,Re o,Re x){
if(o<0)return 0;Re i=(x>>o)&1;
if(cnt[tr[q][i^1]]>cnt[tr[p][i^1]])return (1<<o)+ask(tr[p][i^1],tr[q][i^1],o-1,x);
else return ask(tr[p][i],tr[q][i],o-1,x);
}
}T1;
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
vector<Query>tr[N<<2];
inline void change(Re p,Re L,Re R,Re l,Re r,Query &v){
if(l>r)return;
if(l<=L&&R<=r){tr[p].push_back(v);return;}
if(l<=mid)change(pl,L,mid,l,r,v);
if(r>mid)change(pr,mid+1,R,l,r,v);
}
inline int find1(Re l,Re r,Re id){
if(C[r].i<id)return r+1;
while(l<r){
Re Mid=l+r>>1;
if(C[Mid].i>=id)r=Mid;
else l=Mid+1;
}
return r;
}
inline int find2(Re l,Re r,Re id){
if(C[r].i<=id)return r+1;
while(l<r){
Re Mid=l+r>>1;
if(C[Mid].i>id)r=Mid;
else l=Mid+1;
}
return r;
}
inline void CDQ(Re p,Re L,Re R,Re l,Re r){
if(l>r)return;
T1.O=pt[l-1]=0;
for(Re i=l;i<=r;++i)T1.insert(pt[i]=++T1.O,pt[i-1],logN,C[i].v);
for(vector<Query>::iterator it=tr[p].begin();it!=tr[p].end();++it){
Re ll=find1(l,r,it->l)-1,rr=find2(l,r,it->r)-1;
if(ll<rr)Ans[it->id]=max(Ans[it->id],T1.ask(pt[ll],pt[rr],logN,it->x));
}
if(L==R)return;
Re p1=l-1;for(Re i=l;i<=r;++i)if(C[i].t<=mid)tmp[++p1]=C[i];
Re p2=p1;for(Re i=l;i<=r;++i)if(C[i].t>mid)tmp[++p2]=C[i];
for(Re i=l;i<=r;++i)C[i]=tmp[i];
CDQ(pl,L,mid,l,p1),CDQ(pr,mid+1,R,p1+1,r);
}
}TR;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=1;i<=n;++i)in(A[i]),T1.insert(pt[i]=++T1.O,pt[i-1],logN,A[i]);
for(Re i=1;i<=T;++i){
in(op),in(x),in(y);
if(!op)++m1,C[m1]=(Change){x,y,m1};
else in(z),in(w),++m2,Q[m2]=(Query){z,x,y,m2},t1[m2]=max(1,m1-w+1),t2[m2]=m1;
}
for(Re i=1;i<=m2;++i)Ans[i]=T1.ask(pt[Q[i].l-1],pt[Q[i].r],logN,Q[i].x),TR.change(1,1,m1,t1[i],t2[i],Q[i]);
sort(C+1,C+m1+1),TR.CDQ(1,1,m1,1,m1);
for(Re i=1;i<=m2;++i)printf("%d\n",Ans[i]);
}
struct TreeNode {
int key;
TreeNode* left;
TreeNode* right;
int height; // 节点高度
int size; // 子树大小
int count; // 重复次数
TreeNode(int value)
: key(value), height(1), size(1), count(1), left(nullptr), right(nullptr) {}
};
class BalancedBST {
private:
TreeNode* root;
// 获取节点高度
int getHeight(TreeNode* node) const {
return node ? node->height : 0;
}
// 获取节点子树大小
int getSize(TreeNode* node) const {
return node ? node->size : 0;
}
// 更新节点高度和大小
void updateNodeInfo(TreeNode* node) const {
if (node) {
node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));
node->size = node->count + getSize(node->left) + getSize(node->right);
}
}
// 获取平衡因子
int getBalanceFactor(TreeNode* node) const {
return node ? getHeight(node->left) - getHeight(node->right) : 0;
}
// 右旋
TreeNode* rightRotate(TreeNode* y) const {
TreeNode* x = y->left;
TreeNode* T2 = x->right;
x->right = y;
y->left = T2;
updateNodeInfo(y);
updateNodeInfo(x);
return x;
}
// 左旋
TreeNode* leftRotate(TreeNode* x) const {
TreeNode* y = x->right;
TreeNode* T2 = y->left;
y->left = x;
x->right = T2;
updateNodeInfo(x);
updateNodeInfo(y);
return y;
}
// 平衡节点
TreeNode* balanceNode(TreeNode* node) const {
if (!node) return nullptr;
updateNodeInfo(node);
int balance = getBalanceFactor(node);
// Left Left Case
if (balance > 1 && getBalanceFactor(node->left) >= 0)
return rightRotate(node);
// Right Right Case
if (balance < -1 && getBalanceFactor(node->right) <= 0)
return leftRotate(node);
// Left Right Case
if (balance > 1 && getBalanceFactor(node->left) < 0) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && getBalanceFactor(node->right) > 0) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
// 递归插入
TreeNode* insertHelper(TreeNode* node, int value){
if (!node) {
return new TreeNode(value);
}
if (value < node->key) {
node->left = insertHelper(node->left, value);
} else if (value > node->key) {
node->right = insertHelper(node->right, value);
} else {
node->count++;
node->size++;
return node;
}
return balanceNode(node);
}
// 查找最小节点
TreeNode* findMinNode(TreeNode* node) const {
while (node && node->left) {
node = node->left;
}
return node;
}
// 递归删除
TreeNode* removeHelper(TreeNode* node, int value){
if (!node) return nullptr;
if (value < node->key) {
node->left = removeHelper(node->left, value);
} else if (value > node->key) {
node->right = removeHelper(node->right, value);
} else {
if (node->count > 1) {
node->count--;
node->size--;
return node;
}
if (!node->left || !node->right) {
TreeNode* temp = node->left ? node->left : node->right;
if (!temp) {
delete node;
return nullptr;
} else {
*node = *temp;
delete temp;
}
} else {
TreeNode* successor = findMinNode(node->right);
node->key = successor->key;
node->count = successor->count;
successor->count = 1;
node->right = removeHelper(node->right, successor->key);
}
}
return balanceNode(node);
}
// 递归查找
bool searchHelper(TreeNode* node, int value) const {
if (!node) return false;
if (value == node->key) return true;
if (value < node->key) return searchHelper(node->left, value);
return searchHelper(node->right, value);
}
// 递归中序遍历
void inorderHelper(TreeNode* node, std::vector<int>& result) const {
if (!node) return;
inorderHelper(node->left, result);
for (int i = 0; i < node->count; ++i) {
result.push_back(node->key);
}
inorderHelper(node->right, result);
}
// 递归查询排名
int rankHelper(TreeNode* node, int value) const {
if (!node) return 0;
if (value < node->key) {
return rankHelper(node->left, value);
} else if (value > node->key) {
return getSize(node->left) + node->count + rankHelper(node->right, value);
} else {
return getSize(node->left) + 1;
}
}
// 递归按排名查找
int selectHelper(TreeNode* node, int k) const {
if (!node) return -1;
int leftSize = getSize(node->left);
if (k <= leftSize) {
return selectHelper(node->left, k);
} else if (k <= leftSize + node->count) {
return node->key;
} else {
return selectHelper(node->right, k - leftSize - node->count);
}
}
// 递归释放所有节点
void clearHelper(TreeNode* node) {
if (!node) return;
clearHelper(node->left);
clearHelper(node->right);
delete node;
}
public:
BalancedBST() : root(nullptr) {}
// 插入元素 - O(log n)
void insert(int value) {
root = insertHelper(root, value);
}
// 删除元素 - O(log n)
void remove(int value) {
root = removeHelper(root, value);
}
// 查找元素 - O(log n)
bool search(int value) const {
return searchHelper(root, value);
}
// 获取最小值 - O(log n)
int min() const {
TreeNode* node = findMinNode(root);
return node ? node->key : -1;
}
// 获取最大值 - O(log n)
int max() const {
TreeNode* node = root;
while (node && node->right) {
node = node->right;
}
return node ? node->key : -1;
}
// 中序遍历 - O(n)
std::vector<int> inorder() const {
std::vector<int> result;
inorderHelper(root, result);
return result;
}
// 查询排名 - O(log n)
int rank(int value) const {
return rankHelper(root, value);
}
// 按排名查找 - O(log n)
int select(int k) const {
return selectHelper(root, k);
}
// 清空整棵树
void clear() {
clearHelper(root);
root = nullptr;
}
// 获取树的大小 - O(1)
int size() const {
return getSize(root);
}
// 获取树的高度 - O(1)
int height() const {
return getHeight(root);
}
};#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#define Re register int
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
#define pv tr[p].v
using namespace std;
const int N=1e5+5,inf=2e9;
int T,x,y,n,o,root,a[N];
struct Splay{int v,fa,ps[2],tag,cnt,size;}tr[N];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void pushup(Re p){if(!p)return;tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void connect(Re p,Re f,Re o){tr[tr[p].fa=f].ps[o]=p;}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void pushdown(Re p){
if(tr[p].tag)tr[p].tag=0,swap(pl,pr),tr[pl].tag^=1,tr[pr].tag^=1;
}
inline void rotate(Re p){
Re y=pf,ys=which(p);
Re R=tr[y].fa,Rs=which(y);
Re B=tr[p].ps[ys^1];
connect(B,y,ys),connect(y,p,ys^1),connect(p,R,Rs);
pushup(y),pushup(p);
}
inline void Splay(Re p,Re to){
for(Re fa;(fa=pf)!=to;rotate(p))
if(tr[fa].fa!=to)rotate(which(p)==which(fa)?fa:p);
if(!to)root=p;
}
inline void New(Re x,Re fa){
tr[++o].v=x,tr[o].fa=fa,tr[o].cnt=tr[o].size=1;
if(fa)tr[fa].ps[tr[fa].v<x]=o;
}
inline int ask_w(Re p,Re x){
pushdown(p);
if(x<=tr[pl].size)return ask_w(pl,x);
else{
Re tmp=tr[pl].size+tr[p].cnt;
return x<=tmp?p:ask_w(pr,x-tmp);
}
}
inline void build(Re &p,Re L,Re R,Re fa){
if(L>R)return;
Re mid=L+R>>1;p=++o;
pf=fa,pv=a[mid];
tr[p].cnt=tr[p].size=1;
build(pl,L,mid-1,p),build(pr,mid+1,R,p);
pushup(p);
}
inline void reverse(Re l,Re r){
l=ask_w(root,l-1),r=ask_w(root,r+1);
Splay(l,0),Splay(r,l);
tr[tr[r].ps[0]].tag^=1;
}
inline void print(Re p){
pushdown(p);
if(pl)print(pl);
if(pv!=inf&&pv!=-inf)printf("%d ",pv);
if(pr)print(pr);
}
int main(){
in(n),in(T);
a[1]=-inf,a[n+2]=inf;
for(Re i=2;i<=n+1;++i)a[i]=i-1;
build(root,1,n+2,0);
while(T--)in(x),in(y),reverse(x+1,y+1);
print(root);
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#define Re register int
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
#define pv tr[p].v
using namespace std;
const int N=1e5+5,inf=2e9;
int T,x,y,n,o,root,a[N];
struct Splay{int v,fa,ps[2],tag,cnt,size;}tr[N];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void pushup(Re p){if(!p)return;tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void connect(Re p,Re f,Re o){tr[tr[p].fa=f].ps[o]=p;}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void pushdown(Re p){
if(tr[p].tag)tr[p].tag=0,swap(pl,pr),tr[pl].tag^=1,tr[pr].tag^=1;
}
inline void rotate(Re p){
Re y=pf,ys=which(p);
Re R=tr[y].fa,Rs=which(y);
Re B=tr[p].ps[ys^1];
connect(B,y,ys),connect(y,p,ys^1),connect(p,R,Rs);
pushup(y),pushup(p);
}
inline void Splay(Re p,Re to){
for(Re fa;(fa=pf)!=to;rotate(p))
if(tr[fa].fa!=to)rotate(which(p)==which(fa)?fa:p);
if(!to)root=p;
}
inline void New(Re x,Re fa){
tr[++o].v=x,tr[o].fa=fa,tr[o].cnt=tr[o].size=1;
if(fa)tr[fa].ps[tr[fa].v<x]=o;
}
inline int ask_w(Re p,Re x){
pushdown(p);
if(x<=tr[pl].size)return ask_w(pl,x);
else{
Re tmp=tr[pl].size+tr[p].cnt;
return x<=tmp?p:ask_w(pr,x-tmp);
}
}
inline void build(Re &p,Re L,Re R,Re fa){
if(L>R)return;
Re mid=L+R>>1;p=++o;
pf=fa,pv=a[mid];
tr[p].cnt=tr[p].size=1;
build(pl,L,mid-1,p),build(pr,mid+1,R,p);
pushup(p);
}
inline void reverse(Re l,Re r){
l=ask_w(root,l-1),r=ask_w(root,r+1);
Splay(l,0),Splay(r,l);
tr[tr[r].ps[0]].tag^=1;
}
inline void print(Re p){
pushdown(p);
if(pl)print(pl);
if(pv!=inf&&pv!=-inf)printf("%d ",pv);
if(pr)print(pr);
}
int main(){
in(n),in(T);
a[1]=-inf,a[n+2]=inf;
for(Re i=2;i<=n+1;++i)a[i]=i-1;
build(root,1,n+2,0);
while(T--)in(x),in(y),reverse(x+1,y+1);
print(root);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=2e5+3,inf=1e9;
int n,x,y,z,T,A[N];char op[20];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Splay{
#define pl (tr[p].ps[0])
#define pr (tr[p].ps[1])
#define pf (tr[p].fa)
#define pv (tr[p].v)
int O,root,Q[N];queue<int>D;
struct QAQ{int v,S,fa,max,lmax,rmax,size,ps[2];bool tag,turn;}tr[N];
inline void pushup(Re p){
tr[p].S=tr[pl].S+tr[pr].S+pv;
tr[p].size=tr[pl].size+tr[pr].size+1;
tr[p].lmax=max(tr[pl].lmax,tr[pl].S+pv+tr[pr].lmax);
tr[p].rmax=max(tr[pr].rmax,tr[pr].S+pv+tr[pl].rmax);
tr[p].max=max(tr[pl].rmax+pv+tr[pr].lmax,max(tr[pl].max,tr[pr].max));
}
inline void updata(Re p){tr[p].turn^=1,swap(pl,pr),swap(tr[p].lmax,tr[p].rmax);}
inline void updata(Re p,Re v){
tr[p].tag=1,tr[p].S=(pv=v)*tr[p].size;
if(v>0)tr[p].lmax=tr[p].rmax=tr[p].max=tr[p].S;
else tr[p].lmax=tr[p].rmax=0,tr[p].max=v;
}
inline void pushdown(Re p){
if(tr[p].tag){
if(pl)updata(pl,pv);
if(pr)updata(pr,pv);
tr[p].tag=tr[p].turn=0;
}
if(tr[p].turn){
if(pl)updata(pl);
if(pr)updata(pr);
tr[p].turn=0;
}
}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
inline void rotate(Re p){
Re fa=pf,fas=which(p);
Re pa=tr[fa].fa,pas=which(fa);
Re x=tr[p].ps[fas^1];
connect(x,fa,fas),connect(fa,p,fas^1),connect(p,pa,pas);
pushup(fa),pushup(p);
}
inline void splay(Re p,Re to){
Re x=p,t=0;Q[++t]=x;
while(tr[x].fa)Q[++t]=x=tr[x].fa;
while(t)pushdown(Q[t--]);
for(Re fa;pf!=to;rotate(p))
if(tr[fa=pf].fa!=to)rotate(which(p)==which(fa)?fa:p);
if(!to)root=p;
}
inline void CL(Re p){
tr[p].size=tr[p].turn=tr[p].tag=tr[p].lmax=tr[p].rmax=tr[p].S=pv=pf=pl=pr=0,tr[p].max=-inf;
}
inline int New(){
Re p;
if(D.empty())p=++O;
else p=D.front(),D.pop();
CL(p),tr[p].size=1;return p;
}
inline void build(Re &p,Re L,Re R,Re fa){
if(L>R)return;Re mid=(L+R)>>1;p=New(),pv=A[mid],pf=fa;
build(pl,L,mid-1,p),build(pr,mid+1,R,p);
pushup(p);
}
inline void recycle(Re p){
if(pl)recycle(pl);
if(pr)recycle(pr);
D.push(p),CL(p);
}
inline int find(Re p,Re K){
pushdown(p);
if(K<=tr[pl].size)return find(pl,K);
return K<=tr[pl].size+1?p:find(pr,K-tr[pl].size-1);
}
inline int split(Re L,Re R){
Re p=find(root,L-1),q=find(root,R+1);
splay(p,0),splay(q,p);return tr[q].ps[0];
}
inline void insert(Re st,Re m){
for(Re i=1;i<=m;++i)in(A[i]);
Re rt=0;build(rt,1,m,0);
Re p=find(root,st),q=find(root,st+1);
splay(p,0),splay(q,p);
connect(rt,q,0),pushup(q),pushup(p);
}
inline void erase(Re L,Re R){
Re p=split(L,R),fa=pf;
tr[fa].ps[0]=pf=0,recycle(p);
pushup(fa),pushup(tr[fa].fa);
}
inline int ask(Re L,Re R){return tr[split(L,R)].S;}
inline int ask_max(Re L,Re R){return tr[split(L,R)].max;}
inline void change(Re L,Re R,Re v){
Re p=split(L,R);updata(p,v),pushup(pf),pushup(tr[pf].fa);
}
inline void reverse(Re L,Re R){
Re p=split(L,R);
if(!tr[p].tag)updata(p),pushup(pf),pushup(tr[pf].fa);
}
}TR;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),TR.tr[0].max=A[1]=A[n+2]=-inf;
for(Re i=2;i<=n+1;++i)in(A[i]);
TR.build(TR.root,1,n+2,0);
while(T--){
scanf("%s",op);
if(op[0]=='M'&&op[2]=='X')in(x),in(y),++x,printf("%d\n",TR.ask_max(x,x+y-1));
else if(op[0]=='G'&&(int)strlen(op)==3)in(x),++x,printf("%d\n",TR.ask(x,x));
else{
in(x),in(y),++x;
if(op[0]=='I')TR.insert(x,y);
if(op[0]=='D')TR.erase(x,x+y-1);
if(op[0]=='M')in(z),TR.change(x,x+y-1,z);
if(op[0]=='R')TR.reverse(x,x+y-1);
if(op[0]=='G')printf("%d\n",TR.ask(x,x+y-1));
}
}
}
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=1e5+5;
int x,T,op;
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Splay{
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
#define pv tr[p].v
int O,root;
struct QAQ{int v,fa,cnt,size,ps[2];}tr[N];
inline void pushup(Re p){
if(p)tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;
}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
inline void rotate(Re p){
Re fa=pf,fas=which(p);
Re pa=tr[fa].fa,pas=which(fa);
Re x=tr[p].ps[fas^1];
connect(x,fa,fas),connect(fa,p,fas^1),connect(p,pa,pas);
pushup(fa),pushup(p);
}
inline void splay(Re p){
for(Re fa;fa=pf;rotate(p))
if(tr[fa].fa)rotate(which(p)==which(fa)?fa:p);
root=p;
}
inline int ask_level(Re p,Re x){
if(x==pv){Re ans=tr[pl].size+1;splay(p);return ans;}
return x<pv?ask_level(pl,x):tr[pl].size+tr[p].cnt+ask_level(pr,x);
}
inline int ask_v(Re p,Re k){
if(!p)return 0;
if(k<=tr[pl].size)return ask_v(pl,k);
Re tmp=tr[pl].size+tr[p].cnt;
return k<=tmp?pv:ask_v(pr,k-tmp);
}
inline int pre(Re p){p=pl;while(pr)p=pr;return p;}
inline int nex(Re p){p=pr;while(pl)p=pl;return p;}
inline void insert(Re x){
Re p=root,fa=0;
while(p&&pv!=x)fa=p,p=tr[p].ps[x>pv];
if(p)++tr[p].cnt,pushup(p);
else{
tr[p=++O]=(QAQ){x,fa,1,1};
if(fa)tr[fa].ps[x>tr[fa].v]=p;
}
splay(p);
}
inline void del(Re x){
ask_level(root,x);Re p=root;
if(tr[p].cnt>1){--tr[p].cnt,pushup(p);return;}
if(!pl&&!pr){root=0;return;}
if(!pl||!pr){tr[root=pl+pr].fa=0;return;}
splay(pre(p));
tr[root].ps[1]=pr,tr[pr].fa=root;
pushup(root);
}
inline int ask_pre(Re x){insert(x);Re ans=tr[pre(root)].v;del(x);return ans;}
inline int ask_nex(Re x){insert(x);Re ans=tr[nex(root)].v;del(x);return ans;}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(T);
while(T--){
in(op),in(x);
if(op==1)T1.insert(x);
if(op==2)T1.del(x);
if(op==3)printf("%d\n",T1.ask_level(T1.root,x));
if(op==4)printf("%d\n",T1.ask_v(T1.root,x));
if(op==5)printf("%d\n",T1.ask_pre(x));
if(op==6)printf("%d\n",T1.ask_nex(x));
}
}
//#pragma GCC optimize(3,"Ofast","inline")
//#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#define Re register int
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
#define pv tr[p].v
using namespace std;
const int N=1e5+5,inf=2e9;
int T,a,b,n,o,root;
struct Splay{int v,fa,ps[2],cnt,size;}tr[N];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void pushup(Re p){if(!p)return;/*�������Ҫ���ж�return����������*/tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void connect(Re p,Re f,Re o){tr[tr[p].fa=f].ps[o]=p;}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void rotate(Re p){
Re y=pf,ys=which(p);
Re R=tr[y].fa,Rs=which(y);
Re B=tr[p].ps[ys^1];
connect(B,y,ys),connect(y,p,ys^1),connect(p,R,Rs);
pushup(y),pushup(p);
}
inline void Splay(Re p){
for(Re fa;fa=pf;rotate(p))
if(tr[fa].fa)rotate(which(p)==which(fa)?fa:p);
root=p;
}
inline void New(Re x,Re fa){
tr[++o].v=x,tr[o].fa=fa,tr[o].cnt=tr[o].size=1;
if(fa)tr[fa].ps[tr[fa].v<x]=o;
}
inline void insert(Re x){
if(!root){New(x,0);root=o;return;}
int p=root,fa=0;
while(1){
if(x==pv){++tr[p].cnt,pushup(p),pushup(fa),Splay(p);break;}
fa=p,p=tr[p].ps[pv<x];
if(!p){New(x,fa),pushup(fa),Splay(o);break;}
}
}
inline int ask_level(Re p,Re x){
//printf("p: %d\n",p);exit(0);
if(x==pv){Re ans=tr[pl].size+1;Splay(p);return ans;}
else return x<pv?ask_level(pl,x):tr[p].cnt+tr[pl].size+ask_level(pr,x);
}
inline int ask_v(Re p,Re x){
if(x<=tr[pl].size)return ask_v(pl,x);
else{
Re tmp=tr[pl].size+tr[p].cnt;
return x<=tmp?pv:ask_v(pr,x-tmp);
}
}
inline int ask_nex_p(Re p){p=pr;while(pl)p=pl;return p;}
inline int ask_pri_p(Re p){p=pl;while(pr)p=pr;return p;}
inline void del(Re x){
ask_level(root,x);Re p=root;
if(tr[p].cnt>1){--tr[p].cnt,--tr[p].size;return;}
if(!pl&&!pr){root=0;return;}
if(!pl||!pr){tr[root=pl+pr].fa=0;return;}
Splay(ask_pri_p(root));
tr[root].ps[1]=pr,tr[pr].fa=root;
pushup(root);
}
int main(){
in(T);
while(T--){
in(a),in(b);
if(a==1)insert(b);
if(a==2)del(b);
if(a==3)printf("%d\n",ask_level(root,b));
if(a==4)printf("%d\n",ask_v(root,b));
if(a==5)insert(b),printf("%d\n",tr[ask_pri_p(root)].v),del(b);
if(a==6)insert(b),printf("%d\n",tr[ask_nex_p(root)].v),del(b);
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#define Re register int
#define pl tr[p].lp
#define pr tr[p].rp
#define pv tr[p].v
using namespace std;
const int N=1e5+5,inf=2e9;
int a,b,o,T,root;
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Treap{int v,rd,lp,rp,cnt,size;}tr[N];
inline void pushup(Re p){tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void lturn(Re &p){
Re q=pr;pr=tr[q].lp,tr[q].lp=p;
pushup(p),pushup(p=q);
}
inline void rturn(Re &p){
Re q=pl;pl=tr[q].rp,tr[q].rp=p;
pushup(p),pushup(p=q);
}
inline void insert(Re &p,Re x){
if(!p){tr[p=++o].v=x,tr[p].cnt=tr[p].size=1,tr[p].rd=rand();return;}
++tr[p].size;
if(x==pv)++tr[p].cnt;
else if(x<pv){
insert(pl,x);
if(tr[pl].rd<tr[p].rd)rturn(p);
}
else{
insert(pr,x);
if(tr[pr].rd<tr[p].rd)lturn(p);
}
}
inline void del(Re &p,Re x){
if(!p)return;
if(x<pv)--tr[p].size,del(pl,x);
else if(x>pv)--tr[p].size,del(pr,x);
else{
if(tr[p].cnt>1)--tr[p].cnt,--tr[p].size;
else{
if(pl*pr==0)p=pl+pr;
else if(tr[pl].rd<tr[pr].rd)rturn(p),del(p,x);
else lturn(p),del(p,x);
}
}
}
inline int ask_level(Re p,Re x){
if(x==pv)return tr[pl].size+1;
else return x<pv?ask_level(pl,x):tr[p].cnt+tr[pl].size+ask_level(pr,x);
}
inline int ask_v(Re p,Re x){
if(x<=tr[pl].size)return ask_v(pl,x);
else{
Re tmp=tr[pl].size+tr[p].cnt;
return x<=tmp?pv:ask_v(pr,x-tmp);
}
}
inline int ask_pri(Re p,Re x){
if(!p)return -inf;
if(x<=pv)return ask_pri(pl,x);
else return max(pv,ask_pri(pr,x));
}
inline int ask_nex(Re p,Re x){
if(!p)return inf;
if(x>=pv)return ask_nex(pr,x);
else return min(pv,ask_nex(pl,x));
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}
int main(){
srand((int)time(NULL));
in(T);
while(T--){
in(a),in(b);
if(a==1)insert(root,b);
if(a==2)del(root,b);
if(a==3)write(ask_level(root,b)),puts("");
if(a==4)write(ask_v(root,b)),puts("");
if(a==5)write(ask_pri(root,b)),puts("");
if(a==6)write(ask_nex(root,b)),puts("");
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#define Re register int
#define pl tr[p].lp
#define pr tr[p].rp
#define pv tr[p].v
using namespace std;
const int N=1e5+5,inf=2e9;
int a,b,o,T,root;
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Treap{int v,rd,lp,rp,cnt,size;}tr[N];
inline void pushup(Re p){tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void lturn(Re &p){
Re q=pr;pr=tr[q].lp,tr[q].lp=p;
pushup(p),pushup(p=q);
}
inline void rturn(Re &p){
Re q=pl;pl=tr[q].rp,tr[q].rp=p;
pushup(p),pushup(p=q);
}
inline void insert(Re &p,Re x){
if(!p){tr[p=++o].v=x,tr[p].cnt=tr[p].size=1,tr[p].rd=rand();return;}
++tr[p].size;
if(x==pv)++tr[p].cnt;
else if(x<pv){
insert(pl,x);
if(tr[pl].rd<tr[p].rd)rturn(p);
}
else{
insert(pr,x);
if(tr[pr].rd<tr[p].rd)lturn(p);
}
}
inline void del(Re &p,Re x){
if(!p)return;
if(x<pv)--tr[p].size,del(pl,x);
else if(x>pv)--tr[p].size,del(pr,x);
else{
if(tr[p].cnt>1)--tr[p].cnt,--tr[p].size;
else{
if(pl*pr==0)p=pl+pr;
else if(tr[pl].rd<tr[pr].rd)rturn(p),del(p,x);
else lturn(p),del(p,x);
}
}
}
inline int ask_level(Re p,Re x){
if(x==pv)return tr[pl].size+1;
else return x<pv?ask_level(pl,x):tr[p].cnt+tr[pl].size+ask_level(pr,x);
}
inline int ask_v(Re p,Re x){
if(x<=tr[pl].size)return ask_v(pl,x);
else{
Re tmp=tr[pl].size+tr[p].cnt;
return x<=tmp?pv:ask_v(pr,x-tmp);
}
}
inline int ask_pri(Re p,Re x){
if(!p)return -inf;
if(x<=pv)return ask_pri(pl,x);
else return max(pv,ask_pri(pr,x));
}
inline int ask_nex(Re p,Re x){
if(!p)return inf;
if(x>=pv)return ask_nex(pr,x);
else return min(pv,ask_nex(pl,x));
}
int main(){
srand((int)time(NULL));
in(T);
while(T--){
in(a),in(b);
if(a==1)insert(root,b);
if(a==2)del(root,b);
if(a==3)printf("%d\n",ask_level(root,b));
if(a==4)printf("%d\n",ask_v(root,b));
if(a==5)printf("%d\n",ask_pri(root,b));
if(a==6)printf("%d\n",ask_nex(root,b));
}
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int x,y,z,n,m,T,t,fu,cnt,tl,tr,a[N],b[N],pt[N],C[N],opt[N],ptl[20],ptr[20];
struct QAQ{int g,lp,rp;}tree[N*250];
struct O_O{int l,r,k;}Q[N];
struct T_T{int i,x;}c[N];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline int ask_kth(Re L,Re R,Re k){
if(L==R)return b[R];
Re tmp=0;
F(i,1,tl)tmp-=tree[tree[ptl[i]].lp].g;
F(i,1,tr)tmp+=tree[tree[ptr[i]].lp].g;
if(tmp>=k){
F(i,1,tl)ptl[i]=tree[ptl[i]].lp;
F(i,1,tr)ptr[i]=tree[ptr[i]].lp;
return ask_kth(L,mid,k);
}
else{
F(i,1,tl)ptl[i]=tree[ptl[i]].rp;
F(i,1,tr)ptr[i]=tree[ptr[i]].rp;
return ask_kth(mid+1,R,k-tmp);
}
}
inline int ask_kth_pre(Re L,Re R,Re k){
tl=tr=0;
for(Re i=L-1;i;i-=i&-i)ptl[++tl]=pt[i];
for(Re i=R;i;i-=i&-i)ptr[++tr]=pt[i];
return ask_kth(1,m,k);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
if(!p)p=++cnt;tree[p].g+=v;
if(L==R)return;
if(w<=mid)add(pl,L,mid,w,v);
else add(pr,mid+1,R,w,v);
}
inline void add_pre(Re x,Re v){
Re w=lo(a[x]);
for(Re i=x;i<=n;i+=i&-i)add(pt[i],1,m,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
if(L==R)return tree[p].g;
if(x<=mid)return ask_level(pl,L,mid,x);
else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
inline int ask_level_pre(Re L,Re R,Re w){
Re ans=0;
for(Re i=R;i;i-=i&-i)ans+=ask_level(pt[i],1,m,w);
for(Re i=L-1;i;i-=i&-i)ans-=ask_level(pt[i],1,m,w);
return ans;
}
int main(){
in(n),in(T),m=n;
F(i,1,n)in(a[i]),b[i]=a[i];
F(i,1,T){
in(opt[i]);
if(opt[i]==3)in(c[i].i),in(c[i].x),b[++m]=c[i].x;
else{
in(Q[i].l),in(Q[i].r),in(Q[i].k);
if(opt[i]!=2)b[++m]=Q[i].k;
}
}
sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
F(i,1,n)add_pre(i,1);
F(i,1,T){
if(opt[i]==1)Q[i].k=lo(Q[i].k),printf("%d\n",ask_level_pre(Q[i].l,Q[i].r,Q[i].k-1)+1);
if(opt[i]==2)printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,Q[i].k));
if(opt[i]==3)add_pre(c[i].i,-1),a[c[i].i]=c[i].x,add_pre(c[i].i,1);
if(opt[i]==4){
Re level=ask_level_pre(Q[i].l,Q[i].r,lo(Q[i].k)-1);
if(!level)printf("%d\n",-inf);
else printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,level));
}
if(opt[i]==5){
Re level=ask_level_pre(Q[i].l,Q[i].r,lo(Q[i].k));
if(level==Q[i].r-Q[i].l+1)printf("%d\n",inf);
else printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,level+1));
}
}
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int x,y,z,n,m,T,t,fu,cnt,tl,tr,a[N],b[N],pt[N],C[N],opt[N],ptl[20],ptr[20];
struct QAQ{int g,lp,rp;}tree[N*250];
struct O_O{int l,r,k;}Q[N];
struct T_T{int i,x;}c[N];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline int ask_kth(Re L,Re R,Re k){
if(L==R)return b[R];
Re tmp=0;
F(i,1,tl)tmp-=tree[tree[ptl[i]].lp].g;
F(i,1,tr)tmp+=tree[tree[ptr[i]].lp].g;
if(tmp>=k){
F(i,1,tl)ptl[i]=tree[ptl[i]].lp;
F(i,1,tr)ptr[i]=tree[ptr[i]].lp;
return ask_kth(L,mid,k);
}
else{
F(i,1,tl)ptl[i]=tree[ptl[i]].rp;
F(i,1,tr)ptr[i]=tree[ptr[i]].rp;
return ask_kth(mid+1,R,k-tmp);
}
}
inline int ask_kth_pre(Re L,Re R,Re k){
tl=tr=0;
for(Re i=L-1;i;i-=i&-i)ptl[++tl]=pt[i];
for(Re i=R;i;i-=i&-i)ptr[++tr]=pt[i];
return ask_kth(1,m,k);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
if(!p)p=++cnt;tree[p].g+=v;
if(L==R)return;
if(w<=mid)add(pl,L,mid,w,v);
else add(pr,mid+1,R,w,v);
}
inline void add_pre(Re x,Re v){
Re w=lo(a[x]);
for(Re i=x;i<=n;i+=i&-i)add(pt[i],1,m,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
if(L==R)return tree[p].g;
if(x<=mid)return ask_level(pl,L,mid,x);
else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
inline int ask_level_pre(Re L,Re R,Re w){
Re ans=0;
for(Re i=R;i;i-=i&-i)ans+=ask_level(pt[i],1,m,w);
for(Re i=L-1;i;i-=i&-i)ans-=ask_level(pt[i],1,m,w);
return ans;
}
int main(){
// printf("%lf\n",(sizeof(tree))/1024.0/1024.0);
// printf("%lf\n",(sizeof(tree)+sizeof(Q)+sizeof(c)+sizeof(a)+sizeof(b)+sizeof(pt)+sizeof(C))/1024.0/1024.0);
in(n),in(T),m=n;
F(i,1,n)in(a[i]),b[i]=a[i];
F(i,1,T){
in(opt[i]);
if(opt[i]==3)in(c[i].i),in(c[i].x),b[++m]=c[i].x;
else{
in(Q[i].l),in(Q[i].r),in(Q[i].k);
if(opt[i]!=2)b[++m]=Q[i].k;
}
}
sort(b+1,b+m+1);
m=unique(b+1,b+m+1)-b-1;
F(i,1,n)add_pre(i,1);
F(i,1,T){
if(opt[i]==1)
Q[i].k=lo(Q[i].k),
printf("%d\n",ask_level_pre(Q[i].l,Q[i].r,Q[i].k-1)+1);
if(opt[i]==2)
printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,Q[i].k));
if(opt[i]==3)
add_pre(c[i].i,-1),a[c[i].i]=c[i].x,add_pre(c[i].i,1);
if(opt[i]==4){
}
if(opt[i]==5){
}
}
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstdio>
#define Re register int
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
#define P(x) if(op[i]==x)
using namespace std;
const int N=1e5+3,inf=2147483647;
int m,T,fu,C[N],a[N],b[N],Q[N],op[N];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void add(Re x,Re v){while(x<=m)C[x]+=v,x+=x&-x;}
inline int ask(Re x){
Re ans=0;
while(x>0)ans+=C[x],x-=x&-x;
return ans;
}
inline int ask_kth(Re k){
Re l=0,r=m;
while(l<r){
Re mid=l+r>>1;
if(ask(mid)>=k)r=mid;
else l=mid+1;
}
return b[l];
}
int main(){
in(T);
F(i,1,T){
in(op[i]),in(Q[i]);
if(op[i]!=4)b[++m]=Q[i];
}
sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
F(i,1,T){
P(1)add(lo(Q[i]),1);
P(2)add(lo(Q[i]),-1);
P(3)printf("%d\n",ask(lo(Q[i])-1)+1);
P(4)printf("%d\n",ask_kth(Q[i]));
P(5)printf("%d\n",ask_kth(ask(lo(Q[i])-1)));
P(6)printf("%d\n",ask_kth(ask(lo(Q[i]))+1));
}
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int m,T,t,fu,cnt,root,a[N],b[N],Q[N],opt[N];
struct QAQ{int g,lp,rp;}tree[N<<1];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline int ask_kth(Re p,Re L,Re R,Re k){
if(L==R)return b[R];
Re tmp=tree[pl].g;
if(tmp>=k)return ask_kth(pl,L,mid,k);
else return ask_kth(pr,mid+1,R,k-tmp);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
if(!p)p=++cnt;tree[p].g+=v;
if(L==R)return;
if(w<=mid)add(pl,L,mid,w,v);
else add(pr,mid+1,R,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
if(!x)return 0;
if(L==R)return tree[p].g;
if(x<=mid)return ask_level(pl,L,mid,x);
else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
int main(){
in(T);
F(i,1,T){
in(opt[i]),in(Q[i]);
if(opt[i]!=4)b[++m]=Q[i];
}
sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
F(i,1,T){
if(opt[i]==1)add(root,1,m,lo(Q[i]),1);
if(opt[i]==2)add(root,1,m,lo(Q[i]),-1);
if(opt[i]==3)printf("%d\n",ask_level(root,1,m,lo(Q[i])-1)+1);
if(opt[i]==4)printf("%d\n",ask_kth(root,1,m,Q[i]));
if(opt[i]==5){
Re level=ask_level(root,1,m,lo(Q[i])-1);
printf("%d\n",ask_kth(root,1,m,level));
}
if(opt[i]==6){
Re level=ask_level(root,1,m,lo(Q[i]));
printf("%d\n",ask_kth(root,1,m,level+1));
}
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#define Re register int
#define pl tr[p].lp
#define pr tr[p].rp
#define pv tr[p].v
using namespace std;
const int N=32780,inf=2e9;
int a,o,T,ans,root;
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Treap{int v,rd,lp,rp,cnt,size;}tr[N];
inline void pushup(Re p){tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void lturn(Re &p){
Re q=pr;pr=tr[q].lp,tr[q].lp=p;
pushup(p),pushup(p=q);
}
inline void rturn(Re &p){
Re q=pl;pl=tr[q].rp,tr[q].rp=p;
pushup(p),pushup(p=q);
}
inline void insert(Re &p,Re x){
if(!p){tr[p=++o].v=x,tr[p].cnt=tr[p].size=1,tr[p].rd=rand();return;}
++tr[p].size;
if(x==pv)++tr[p].cnt;
else if(x<pv){
insert(pl,x);
if(tr[pl].rd<tr[p].rd)rturn(p);
}
else{
insert(pr,x);
if(tr[pr].rd<tr[p].rd)lturn(p);
}
}
inline int ask_pri(Re p,Re x){
if(!p)return -inf;
if(x==pv)return x;
else if(x<pv)return ask_pri(pl,x);
else return max(pv,ask_pri(pr,x));
}
inline int ask_nex(Re p,Re x){
if(!p)return inf;
if(x==pv)return x;
else if(x>pv)return ask_nex(pr,x);
else return min(pv,ask_nex(pl,x));
}
int main(){
srand((int)time(NULL));
in(T);--T;in(a);ans=a;insert(root,a);
while(T--){
in(a);
ans+=min(abs(a-ask_pri(root,a)),abs(a-ask_nex(root,a)));
insert(root,a);
}
printf("%d",ans);
}
#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
int n, m, cnt, root[N], a[N];
int ls[N << 5], rs[N << 5], w[N << 5];
vector<int> b;
int update(int lu, int l, int r, int x) {
int u = ++cnt;
ls[u] = ls[lu]; rs[u] = rs[lu]; w[u] = w[lu] + 1;
if (l == r) return u;
int mid = (l + r) >> 1;
if (x <= mid) ls[u] = update(ls[lu], l, mid, x);
else rs[u] = update(rs[lu], mid + 1, r, x);
return u;
}
// 核心变化:前缀和相减,二分找第 K 小
int query(int u1, int u2, int l, int r, int k) {
if (l == r) return l;
int d = w[ls[u2]] - w[ls[u1]];
int mid = (l + r) >> 1;
if (k <= d) return query(ls[u1], ls[u2], l, mid, k);
else return query(rs[u1], rs[u2], mid + 1, r, k - d);
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
b.push_back(a[i]);
}
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
int max_val = b.size();
for (int i = 1; i <= n; i++) {
int x = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
root[i] = update(root[i - 1], 1, max_val, x);
}
while (m--) {
int l, r, k;
cin >> l >> r >> k;
int ans_rk = query(root[l - 1], root[r], 1, max_val, k);
cout << b[ans_rk - 1] << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}#include<iostream>
#include<stack>
#include<string>
#include<set>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
//#define int long long
const int N=1e6+5;
int n,m,cnt,root[N],last[N];
int ls[N<<5],rs[N<<5],w[N<<5];
int update(int lu,int l,int r,int x){
int u=++cnt;
ls[u]=ls[lu],rs[u]=rs[lu],w[u]=w[lu];w[u]++;
if(l==r)return u;
int mid=(l+r)>>1;
if(x<=mid)ls[u]=update(ls[lu],l,mid,x);
else rs[u]=update(rs[lu],mid+1,r,x);
return u;
}
int query(int u1,int u2,int l,int r,int x){
if(l>=x)return 0;
if(r<x)return w[u2]-w[u1];
int mid=(l+r)>>1;
return query(ls[u1],ls[u2],l,mid,x)+query(rs[u1],rs[u2],mid+1,r,x);
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
if(last[x])root[i]=update(root[i-1],0,n,last[x]);
else root[i]=update(root[i-1],0,n,0);
last[x]=i;
}
cin>>m;
while(m--){
int l,r;
cin>>l>>r;
cout<<query(root[l-1],root[r],0,n,l)<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
while(T--)solve();
}
/*
*/#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
using namespace std;
const int N = 2e5 + 5;
int n, q, cnt, root[N];
int ls[N * 40], rs[N * 40], min_pos[N * 40];
int update(int pre, int l, int r, int x, int pos) {
int u = ++cnt;
ls[u] = ls[pre]; rs[u] = rs[pre];
if (l == r) {
min_pos[u] = pos;
return u;
}
int mid = (l + r) >> 1;
if (x <= mid) ls[u] = update(ls[pre], l, mid, x, pos);
else rs[u] = update(rs[pre], mid + 1, r, x, pos);
min_pos[u] = min(min_pos[ls[u]], min_pos[rs[u]]);
return u;
}
int query(int u, int l, int r, int limit_L) {
if (l == r) return l;
int mid = (l + r) >> 1;
if (min_pos[ls[u]] < limit_L) return query(ls[u], l, mid, limit_L);
else return query(rs[u], mid + 1, r, limit_L);
}
void solve() {
cin >> n >> q;
for (int i = 1, x; i <= n; ++i) {
cin >> x;
if (x > n + 1) {
root[i] = root[i - 1];
} else {
root[i] = update(root[i - 1], 0, n + 1, x, i);
}
}
while (q--) {
int l, r;
cin >> l >> r;
cout << query(root[r], 0, n + 1, l) << '\n';
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
return 0;
}#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
const int N=5e4+3,T=230;
int n,t,x,l,r,Q,fu,pt[N],L[T],R[T];LL a[N],S[T],add[T];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void change(Re l,Re r,Re x){
Re p=pt[l],q=pt[r];
if(p==q){F(i,l,r)a[i]+=x;S[p]+=x*(r-l+1);}
else{
F(i,p+1,q-1)add[i]+=x;
F(i,l,R[p])a[i]+=x;S[p]+=x*(R[p]-l+1);
F(i,L[q],r)a[i]+=x;S[q]+=x*(r-L[q]+1);
}
}
inline LL ask(Re x){return a[x]+add[pt[x]];}
int main(){
in(n),t=sqrt(Q=n);
F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
F(i,1,n)in(x),a[i]=x;
F(i,1,t)F(j,L[i],R[i])pt[j]=i,S[i]+=a[j];
while(Q--){
in(n),in(l),in(r),in(x);
if(n)printf("%lld\n",ask(r));
else change(l,r,x);
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
#define lo(l,r,x) (lower_bound(b+l,b+r+1,x)-b)
using namespace std;
const int N=5e4+3,T=230;
int n,t,x,l,r,o,Q,fu,pt[N],L[T],R[T];LL a[N],b[N],add[T];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void sak(Re l,Re r,Re p,Re x){F(i,l,r)a[i]+=x;F(i,L[p],R[p])b[i]=a[i];sort(b+L[p],b+R[p]+1);}
inline void change(Re l,Re r,Re x){
Re p=pt[l],q=pt[r];
if(p==q)sak(l,r,p,x);
else{
F(i,p+1,q-1)add[i]+=x;
sak(l,R[p],p,x),sak(L[q],r,q,x);
}
}
inline LL ask(Re l,Re r,LL x){
Re p=pt[l],q=pt[r];LL ans=0;
if(p==q){F(i,l,r)ans+=a[i]+add[p]<x;return ans;}
else{
F(i,p+1,q-1)ans+=lo(L[i],R[i],x-add[i])-L[i];
F(i,l,R[p])ans+=a[i]+add[p]<x;
F(i,L[q],r)ans+=a[i]+add[q]<x;
}
return ans;
}
int main(){
in(n),t=sqrt(Q=n);
F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
F(i,1,n)in(x),a[i]=b[i]=x;
F(i,1,t)F(j,L[i],R[i])pt[j]=i;
F(i,1,t)sort(b+L[i],b+R[i]+1);
while(Q--){
in(o),in(l),in(r),in(x);
if(o)printf("%lld\n",ask(l,r,(LL)x*x));
else change(l,r,x);
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#include<cmath>
#define inf -2147483647
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
using namespace std;
const int N=1e5+3,T=330;
int n,t,x,l,r,o,Q,fu,pt[N],L[T],R[T],a[N],b[N],add[T];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void sak(Re l,Re r,Re p,Re x){F(i,l,r)a[i]+=x;F(i,L[p],R[p])b[i]=a[i];sort(b+L[p],b+R[p]+1);}
inline void change(Re l,Re r,Re x){
Re p=pt[l],q=pt[r];
if(p==q)sak(l,r,p,x);
else{
F(i,p+1,q-1)add[i]+=x;
sak(l,R[p],p,x),sak(L[q],r,q,x);
}
}
inline int ask(Re l,Re r,Re x){
Re p=pt[l],q=pt[r],ans=inf,w;
if(p==q){F(i,l,r)if(a[i]+add[p]<x)ans=max(ans,a[i]+add[p]);}
else{
F(i,p+1,q-1)w=lower_bound(b+L[i],b+R[i]+1,x-add[i])-(b+1),ans=w>=L[i]?max(ans,b[w]+add[i]):ans;
F(i,l,R[p])if(a[i]+add[p]<x)ans=max(ans,a[i]+add[p]);
F(i,L[q],r)if(a[i]+add[q]<x)ans=max(ans,a[i]+add[q]);
}
return ans==inf?-1:ans;
}
int main(){
in(n),t=sqrt(Q=n);
F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
F(i,1,n)in(x),a[i]=b[i]=x;
F(i,1,t)F(j,L[i],R[i])pt[j]=i;
F(i,1,t)sort(b+L[i],b+R[i]+1);
while(Q--){
in(o),in(l),in(r),in(x);
if(o)printf("%d\n",ask(l,r,x));
else change(l,r,x);
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
const int N=5e4+3,T=230;
int n,t,x,l,r,Q,fu,pt[N],L[T],R[T];LL a[N],S[T],add[T];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void change(Re l,Re r,Re x){
Re p=pt[l],q=pt[r];
if(p==q){F(i,l,r)a[i]+=x;S[p]+=(LL)x*(r-l+1);}
else{
F(i,p+1,q-1)add[i]+=x;
F(i,l,R[p])a[i]+=x;S[p]+=(LL)x*(R[p]-l+1);
F(i,L[q],r)a[i]+=x;S[q]+=(LL)x*(r-L[q]+1);
}
}
inline LL ask(Re l,Re r){
Re p=pt[l],q=pt[r];LL ans=0;
if(p==q){F(i,l,r)ans+=a[i];ans+=add[p]*(r-l+1);}
else{
F(i,p+1,q-1)ans+=S[i]+add[i]*(LL)(R[i]-L[i]+1);
F(i,l,R[p])ans+=a[i];ans+=add[p]*(LL)(R[p]-l+1);
F(i,L[q],r)ans+=a[i];ans+=add[q]*(LL)(r-L[q]+1);
}
return ans;
}
int main(){
in(n),t=sqrt(Q=n);
F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
F(i,1,n)in(x),a[i]=x;
F(i,1,t)F(j,L[i],R[i])pt[j]=i,S[i]+=a[j];
while(Q--){
in(n),in(l),in(r),in(x);
if(n)printf("%lld\n",ask(l,r)%(x+1));
else change(l,r,x);
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
const int N=5e4+3,T=230;
int n,t,x,l,r,Q,fu,pt[N],L[T],R[T],pan[T];LL a[N],S[T];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void sakura(Re p){
if(pan[p])return;pan[p]=1,S[p]=0;
F(i,L[p],R[p])S[p]+=(a[i]=sqrt(a[i])),pan[p]&=(a[i]<=1);
}
inline void change(Re l,Re r){
Re p=pt[l],q=pt[r];
if(p==q){F(i,l,r)S[p]-=a[i],a[i]=sqrt(a[i]),S[p]+=a[i];}
else{
F(i,p+1,q-1)sakura(i);
F(i,l,R[p])S[p]-=a[i],a[i]=sqrt(a[i]),S[p]+=a[i];
F(i,L[q],r)S[q]-=a[i],a[i]=sqrt(a[i]),S[q]+=a[i];
}
}
inline LL ask(Re l,Re r){
Re p=pt[l],q=pt[r];LL ans=0;
if(p==q){F(i,l,r)ans+=a[i];}
else{
F(i,p+1,q-1)ans+=S[i];
F(i,l,R[p])ans+=a[i];
F(i,L[q],r)ans+=a[i];
}
return ans;
}
int main(){
in(n),t=sqrt(Q=n);
F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
F(i,1,n)in(x),a[i]=x;
F(i,1,t)F(j,L[i],R[i])pt[j]=i,S[i]+=a[j];
while(Q--){
in(n),in(l),in(r),in(x);
if(n)printf("%lld\n",ask(l,r));
else change(l,r);
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<vector>
#include<cstdio>
#include<cmath>
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
using namespace std;
const int N=1e5+3,T=330;
int n,o,t,x,l,r,Q,fu,pt[N],pw[N],L[T],R[T];
vector<int>a[T];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void change(Re w,Re x){
F(i,1,t)
if(w>a[i].size())w-=a[i].size();
else{a[i].insert(a[i].begin()+w-1,x);return;}
}
inline int ask(Re w){
F(i,1,t)
if(w>a[i].size())w-=a[i].size();
else return a[i][w-1];
}
int main(){
in(n),t=sqrt(Q=n);
F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
F(i,1,t){F(j,L[i],R[i])in(x),a[i].push_back(x),pt[j]=i;}
while(Q--){
in(o),in(l),in(r),in(x);
if(o)printf("%d\n",ask(r));
else change(l,r);
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
const int N=1e5+3,T=320;
int n,t,x,l,r,Q,fu,P=10007,pt[N],L[T],R[T],a[N],add[T],mul[T];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void spread(Re p){
F(i,L[p],R[p])(((a[i]*=mul[p])%=P)+=add[p])%=P;
add[p]=0,mul[p]=1;
}
inline void change(Re l,Re r,Re x){
Re p=pt[l],q=pt[r];spread(p);
if(p==q)F(i,l,r)(a[i]+=x)%=P;
else{
spread(q);
F(i,p+1,q-1)(add[i]+=x)%P;
F(i,l,R[p])(a[i]+=x)%=P;
F(i,L[q],r)(a[i]+=x)%=P;
}
}
inline void change2(Re l,Re r,Re x){
Re p=pt[l],q=pt[r];spread(p);
if(p==q)F(i,l,r)(a[i]*=x)%=P;
else{
spread(q);
F(i,p+1,q-1)(add[i]*=x)%=P,(mul[i]*=x)%=P;
F(i,l,R[p])(a[i]*=x)%=P;
F(i,L[q],r)(a[i]*=x)%=P;
}
}
inline int ask(Re x){return (a[x]*mul[pt[x]]%P+add[pt[x]])%P;}
int main(){
in(n),t=sqrt(Q=n);
F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t,mul[i]=1;
if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1,mul[t]=1;
F(i,1,n)in(a[i]);
F(i,1,t)F(j,L[i],R[i])pt[j]=i;
while(Q--){
in(n),in(l),in(r),in(x);
if(n>1)printf("%d\n",ask(r));
else n?change2(l,r,x%P):change(l,r,x%P);
}
}
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<cstdio>
#include<cmath>
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
const int N=1e5+3,T=330;
int n,t,x,l,r,Q,fu,pt[N],L[T],R[T],a[N],tag[T];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline int sak(Re l,Re r,Re p,Re x){
Re tmp=0;
if(tag[p]!=-1){F(i,L[p],R[p])a[i]=tag[p];tmp+=(r-l+1)*(tag[p]==x);}
else F(i,l,r)tmp+=a[i]==x;
tag[p]=-1;F(i,l,r)a[i]=x;
return tmp;
}
inline int fuck(Re p,Re x){
Re tmp=0;
if(tag[p]!=-1){F(j,L[p],R[p])a[j]=tag[p];tmp+=(R[p]-L[p]+1)*(tag[p]==x);}
else F(j,L[p],R[p])tmp+=a[j]==x;
tag[p]=x;
return tmp;
}
inline int sovle(Re l,Re r,Re x){
Re p=pt[l],q=pt[r],ans=0;
if(p==q)return l==r?fuck(p,x):sak(l,r,p,x);
else{
F(i,p+1,q-1)ans+=fuck(i,x);
ans+=sak(l,R[p],p,x)+sak(L[q],r,q,x);
}
return ans;
}
int main(){
in(n),t=sqrt(Q=n);
F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
F(i,1,n)in(x),a[i]=x;
F(i,1,t){tag[i]=-1;F(j,L[i],R[i])pt[j]=i;}
while(Q--){
in(l),in(r),in(x);
printf("%d\n",sovle(l,r,x));
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,M=1e5+3;
int n,m,T,BL,BLN,A[N],b[N],Li[325],Ri[325],cnt[N],cnt_[N],belong[N];LL Ans[M];
struct Query{
int l,r,id;
inline bool operator<(const Query &O)const{
Re B1=belong[l],B2=belong[O.l];
return B1!=B2?B1<B2:r<O.r;
}
}Q[M];
inline void in(Re &x){
Re fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),BL=sqrt(n)+1,BLN=n/BL+1;
for(Re i=1;i<=BLN;++i){
Li[i]=(i-1)*BL+1,Ri[i]=min(i*BL,n);
for(Re j=Li[i];j<=Ri[i];++j)belong[j]=i;
}
for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
sort(b+1,b+n+1),m=unique(b+1,b+n+1)-b-1;
for(Re i=1;i<=n;++i)A[i]=lower_bound(b+1,b+m+1,A[i])-b;
for(Re i=1;i<=T;++i)in(Q[i].l),in(Q[i].r),Q[i].id=i;
sort(Q+1,Q+T+1);Re i=1;
for(Re p=1;p<=BLN;++p){
Re nowL=Ri[p]+1,nowR=Ri[p];LL ans=0;
memset(cnt,0,sizeof(cnt));
while(belong[Q[i].l]==p){
Re L=Q[i].l,R=Q[i].r;
if(belong[L]==belong[R]){
LL tmp=0;
for(Re j=L;j<=R;++j)cnt_[A[j]]=0;
for(Re j=L;j<=R;++j)++cnt_[A[j]],tmp=max(tmp,(LL)b[A[j]]*cnt_[A[j]]);
Ans[Q[i].id]=tmp;
}
else{
while(nowR<R)cnt[A[++nowR]]++,ans=max(ans,(LL)b[A[nowR]]*cnt[A[nowR]]);
LL tmp=ans;
while(nowL>L)cnt[A[--nowL]]++,tmp=max(tmp,(LL)b[A[nowL]]*cnt[A[nowL]]);
Ans[Q[i].id]=tmp;
while(nowL<Ri[p]+1)--cnt[A[nowL++]];
}
++i;
}
}
for(Re i=1;i<=T;++i)printf("%lld\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define Re register int
using namespace std;
const int N=2e5+3,M=2e5+3,INF=1e6+3;
int n,x,y,T,TQ,TC,BL,ans,a[N],Ans[M],cnt[INF];char op;
struct Query{
int l,r,id,time;
inline bool operator<(const Query &O)const{
Re B1=l/BL,B2=O.l/BL,B3=r/BL,B4=O.r/BL;
return B1!=B2?B1<B2:(B3!=B4?B3<B4:time<O.time);
}
}Q[N];
struct Change{int w,co;}C[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x){ans+=!cnt[x]++;}
inline void del(Re x){ans-=!--cnt[x];}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),BL=pow(n,2.0/3.0);
for(Re i=1;i<=n;++i)in(a[i]);
for(Re i=1;i<=T;++i){
scanf(" %c",&op);
in(x),in(y);
if(op=='Q')++TQ,Q[TQ]=(Query){x,y,TQ,TC};
else C[++TC]=(Change){x,y};
}
sort(Q+1,Q+TQ+1);
Re nowL=1,nowR=0,nowT=0;
for(Re i=1;i<=TQ;++i){
while(nowL<Q[i].l)del(a[nowL++]);
while(nowL>Q[i].l)add(a[--nowL]);
while(nowR>Q[i].r)del(a[nowR--]);
while(nowR<Q[i].r)add(a[++nowR]);
while(nowT<Q[i].time){
Re w=C[++nowT].w;
if(nowL<=w&&w<=nowR)del(a[w]),add(C[nowT].co);
swap(a[w],C[nowT].co);
}
while(nowT>Q[i].time){
Re w=C[nowT].w;
if(nowL<=w&&w<=nowR)del(a[w]),add(C[nowT].co);
swap(a[w],C[nowT--].co);
}
Ans[Q[i].id]=ans;
}
for(Re i=1;i<=TQ;++i)printf("%d\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,M=1e5+3,logN=17;
int n,m,x,y,o,T,op,id_O,A[N],V[N],W[N],B[N],head[N],last[N],first[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
Re fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct LCA{
int deep[N],ant[N][20];
inline void dfs(Re x,Re fa){
first[B[++B[0]]=x]=++id_O;
deep[x]=deep[ant[x][0]=fa]+1;
for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
last[B[++B[0]]=x]=++id_O;
}
inline int lca(Re x,Re y){
if(deep[x]<deep[y])swap(x,y);
for(Re i=logN;i>=0;--i)if(deep[ant[x][i]]>=deep[y])x=ant[x][i];
if(x==y)return x;
for(Re i=logN;i>=0;--i)if(ant[x][i]!=ant[y][i])x=ant[x][i],y=ant[y][i];
return ant[x][0];
}
}T1;
int BL,TQ,TC,vis[N],cnt[N];LL ans,Ans[M];
struct Query{
int l,r,id,lca,time;
inline bool operator<(const Query &O)const{
Re B1=l/BL,B2=O.l/BL,B3=r/BL,B4=O.r/BL;
return B1!=B2?B1<B2:(B3!=B4?B3<B4:time<O.time);
}
}Q[M];
struct Change{int w,co;}C[M];
inline void change(Re x){
vis[x]?ans-=(LL)V[A[x]]*W[cnt[A[x]]--]:ans+=(LL)V[A[x]]*W[++cnt[A[x]]],vis[x]^=1;
}
int main(){
freopen("123.txt","r",stdin);
in(n),in(m),in(T),BL=pow(n<<1,2.0/3.0);
for(Re i=1;i<=m;++i)in(V[i]);
for(Re i=1;i<=n;++i)in(W[i]);
for(Re i=1;i<n;++i)in(x),in(y),add(x,y),add(y,x);
for(Re i=1;i<=n;++i)in(A[i]);
T1.dfs(1,0);
for(Re i=1;i<=T;++i){
in(op),in(x),in(y);
if(op){
Re lca=T1.lca(x,y);
if(first[x]>first[y])swap(x,y);
if(lca==x)++TQ,Q[TQ]=(Query){first[x],first[y],TQ,0,TC};
else ++TQ,Q[TQ]=(Query){last[x],first[y],TQ,lca,TC};
}
else C[++TC]=(Change){x,y};
}
sort(Q+1,Q+TQ+1);
Re nowL=1,nowR=0,nowT=0;
for(Re i=1;i<=TQ;++i){
Re L=Q[i].l,R=Q[i].r,T=Q[i].time,lca=Q[i].lca;
while(nowL<L)change(B[nowL++]);
while(nowL>L)change(B[--nowL]);
while(nowR>R)change(B[nowR--]);
while(nowR<R)change(B[++nowR]);
while(nowT<T){
Re w=C[++nowT].w;
if(vis[w])change(w),swap(A[w],C[nowT].co),change(w);
else swap(A[w],C[nowT].co);
}
while(nowT>T){
Re w=C[nowT].w;
if(vis[w])change(w),swap(A[w],C[nowT].co),change(w);
else swap(A[w],C[nowT].co);
--nowT;
}
if(lca)change(lca);
Ans[Q[i].id]=ans;
if(lca)change(lca);
}
for(Re i=1;i<=TQ;++i)printf("%lld\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=4e4+3,M=1e5+3,INF=1e6+3,logN=16;
int n,m,o,x,y,T,BL,id_O,b[N],A[N],B[N<<1],head[N],last[N],first[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
Re fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct LCA{
int deep[N],ant[N][20];
inline void dfs(Re x,Re fa){
first[B[++B[0]]=x]=++id_O;
deep[x]=deep[ant[x][0]=fa]+1;
for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
last[B[++B[0]]=x]=++id_O;
}
inline int lca(Re x,Re y){
if(deep[x]<deep[y])swap(x,y);
for(Re i=logN;i>=0;--i)if(deep[ant[x][i]]>=deep[y])x=ant[x][i];
if(x==y)return x;
for(Re i=logN;i>=0;--i)if(ant[x][i]!=ant[y][i])x=ant[x][i],y=ant[y][i];
return ant[x][0];
}
}T1;
struct Query{
int l,r,id,lca;
inline bool operator<(const Query &O)const{
Re B1=l/BL,B2=O.l/BL;
return B1!=B2?B1<B2:((B1&1)?r<O.r:r>O.r);
}
}Q[M];
int ans,vis[N<<1],Ans[M],cnt[INF];
inline void change(Re x){
vis[x]?ans-=!--cnt[A[x]]:ans+=!cnt[A[x]]++,vis[x]^=1;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),BL=sqrt(n<<1);
for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
sort(b+1,b+n+1),m=unique(b+1,b+n+1)-b-1;
for(Re i=1;i<=n;++i)A[i]=lower_bound(b+1,b+m+1,A[i])-b;
m=n-1;while(m--)in(x),in(y),add(x,y),add(y,x);
T1.dfs(1,0);
for(Re i=1;i<=T;++i){
in(x),in(y);Re lca=T1.lca(x,y);
if(first[x]>first[y])swap(x,y);
if(lca==x)Q[i]=(Query){first[x],first[y],i,0};
else Q[i]=(Query){last[x],first[y],i,lca};
}
sort(Q+1,Q+T+1);
Re nowL=1,nowR=0;
for(Re i=1;i<=T;++i){
Re L=Q[i].l,R=Q[i].r,lca=Q[i].lca;
while(nowL<L)change(B[nowL++]);
while(nowL>L)change(B[--nowL]);
while(nowR>R)change(B[nowR--]);
while(nowR<R)change(B[++nowR]);
if(lca)change(lca);
Ans[Q[i].id]=ans;
if(lca)change(lca);
}
for(Re i=1;i<=T;++i)printf("%d\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=3e4+3,M=2e5+3;
int n,T,BL,ans,A[N],cnt[1000003],Ans[M];
struct Query{
int l,r,id;
inline bool operator<(const Query &O)const{
Re B1=l/BL,B2=O.l/BL;
return B1!=B2?B1<B2:((B1&1)?r<O.r:r>O.r);
}
}Q[M];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x){ans+=!cnt[x]++;}
inline void del(Re x){ans-=!--cnt[x];}
int main(){
in(n),BL=sqrt(n)+1;
for(Re i=1;i<=n;++i)in(A[i]);
in(T);
for(Re i=1;i<=T;++i)in(Q[i].l),in(Q[i].r),Q[i].id=i;
sort(Q+1,Q+T+1);Re nowL=1,nowR=0;
for(Re i=1;i<=T;++i){
while(nowR<Q[i].r)add(A[++nowR]);
while(nowR>Q[i].r)del(A[nowR--]);
while(nowL>Q[i].l)add(A[--nowL]);
while(nowL<Q[i].l)del(A[nowL++]);
Ans[Q[i].id]=ans;
}
for(Re i=1;i<=T;++i)printf("%d\n",Ans[i]);
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#include<cmath>
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
#define LL long long
using std::sort;
const int N=5e4+3;
int n,q,t,L,R,ip,fu,len,gs[N],pt[N],co[N];LL ans,gcd,fz[N],fm[N];
struct QAQ{int l,r,id;}Q[N];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void sakura(Re p,Re x){ans-=(LL)gs[fu=co[p]]*gs[fu],gs[fu]+=x,ans+=(LL)gs[fu]*gs[fu];}
inline bool cmp(QAQ a,QAQ b){return pt[a.l]==pt[b.l]?a.r<b.r:a.l<b.l;}
inline LL gcd_(LL a,LL b){while(b^=a^=b^=a%=b);return a;}
int main(){
in(n),in(q),t=sqrt(n);
F(i,1,n)in(co[i]),pt[i]=i/t+1;
F(i,1,q)in(Q[i].l),in(Q[i].r),Q[i].id=i;
sort(Q+1,Q+q+1,cmp);
L=1,R=0;
F(i,1,q){
while(L<Q[i].l)sakura(L++,-1);
while(L>Q[i].l)sakura(--L,1);
while(R<Q[i].r)sakura(++R,1);
while(R>Q[i].r)sakura(R--,-1);
ip=Q[i].id;
if(Q[i].l==Q[i].r){fz[ip]=0,fm[ip]=1;continue;}
fz[ip]=ans-(len=Q[i].r-Q[i].l+1);
fm[ip]=(LL)len*(len-1);
gcd=gcd_(fz[ip],fm[ip]),fz[ip]/=gcd,fm[ip]/=gcd;
}
F(i,1,q)printf("%lld/%lld\n",fz[i],fm[i]);
}
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int u=40010;
int c[40][40][u],f[40][40],d[40][40],a[u],b[u],fa[u],fb[u],st[40],ed[40];
int n,m,t,l,tot,i,j,k,x,y,ans,L,R,cnt,num;
void prework()
{
t=(int)pow(n*1.0,1.0/3);
if(t) l=n/t;
for(i=1;i<=t;i++) st[i]=(i-1)*l+1,ed[i]=i*l;
if(ed[t]<n) st[t+1]=ed[t]+1,ed[++t]=n;
memcpy(fa,a,sizeof(a));
sort(fa+1,fa+n+1);
for(i=1;i<=n;i++)
if(i==1||fa[i]!=fa[i-1]) fb[++tot]=fa[i];
for(i=1;i<=n;i++) b[i]=lower_bound(fb+1,fb+tot+1,a[i])-fb;
for(i=1;i<=t;i++)
for(j=i;j<=t;j++)
{
for(k=st[i];k<=ed[j];k++) c[i][j][b[k]]++;
for(k=1;k<=tot;k++)
if(c[i][j][k]>f[i][j]||c[i][j][k]==f[i][j]&&k<d[i][j])
f[i][j]=c[i][j][k],d[i][j]=k;
}
}
inline void update(int i)
{
c[L][R][b[i]]++;
if(c[L][R][b[i]]>cnt||c[L][R][b[i]]==cnt&&b[i]<num) cnt=c[L][R][b[i]],num=b[i];
}
int solve(int x,int y)
{
int i,l,r;
if(x>y) swap(x,y);
for(i=1;i<=t;i++) if(x<=ed[i]) {l=i; break;}
for(i=t;i;i--) if(y>=st[i]) {r=i; break;}
if(l+1<=r-1) L=l+1,R=r-1; else L=R=0;
cnt=f[L][R],num=d[L][R];
if(l==r)
{
for(i=x;i<=y;i++) update(i);
for(i=x;i<=y;i++) c[L][R][b[i]]--;
}
else{
for(i=x;i<=ed[l];i++) update(i);
for(i=st[r];i<=y;i++) update(i);
for(i=x;i<=ed[l];i++) c[L][R][b[i]]--;
for(i=st[r];i<=y;i++) c[L][R][b[i]]--;
}
return fb[num];
}
int main()
{
cin>>n>>m;
for(i=1;i<=n;i++) scanf("%d",&a[i]);
prework();
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
ans=solve((x+ans-1)%n+1,(y+ans-1)%n+1);
printf("%d\n",ans);
}
return 0;
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#include<vector>
#include<set>
#define LL long long
#define Re register int
#define IT set<QAQ>::iterator
using namespace std;
const int N=1e5+5;
struct QAQ{
int l,r;mutable LL v;
QAQ(int L,int R=-1,LL V=0):l(L),r(R),v(V){}
bool operator<(QAQ o)const{return l<o.l;}
};
int l,r,x,y,n,m,fu,op,seed,vmax,a[N];set<QAQ>s;
inline int rnd(){
Re tmp=seed;
seed=((LL)seed*7+13)%1000000007;
return tmp;
}
inline LL mi(LL a,LL k,LL P){
LL ans=1;a%=P;
while(k){
if(k&1)(ans*=a)%=P;
(a*=a)%=P,k>>=1;
}
return ans;
}
inline IT split(Re w){
IT it=s.lower_bound(QAQ(w));
if(it!=s.end()&&it->l==w)return it;
--it;
Re L=it->l,R=it->r;LL V=it->v;
s.erase(it);
s.insert(QAQ(L,w-1,V));
return s.insert(QAQ(w,R,V)).first;
}
inline void assign(Re l,Re r,LL v){
IT itr=split(r+1),itl=split(l);
s.erase(itl,itr),s.insert(QAQ(l,r,v));
}
inline void add(Re l,Re r,LL v){
IT itr=split(r+1),itl=split(l);
while(itl!=itr)itl->v+=v,++itl;
}
inline LL mi_sum(Re l,Re r,Re k,Re P){
IT itr=split(r+1),itl=split(l);LL ans=0;
while(itl!=itr)(ans+=(LL)(itl->r-itl->l+1)%P*mi(itl->v,(LL)k,(LL)P)%P)%=P,++itl;
return ans;
}
inline LL ask_k(Re l,Re r,Re k){
IT itr=split(r+1),itl=split(l);
vector<pair<LL,int> >Q;
Q.clear();
while(itl!=itr)Q.push_back(pair<LL,int>(itl->v,itl->r-itl->l+1)),++itl;
sort(Q.begin(),Q.end());
for(vector<pair<LL,int> >::iterator it=Q.begin();it!=Q.end();++it){
k-=it->second;
if(k<=0)return it->first;
}
}
int main(){
scanf("%d%d%d%d",&n,&m,&seed,&vmax);
for(Re i=1;i<=n;++i)a[i]=(rnd()%vmax)+1,s.insert(QAQ(i,i,a[i]));
s.insert(QAQ(n+1,n+1,0));
while(m--){
op=(rnd()%4)+1,l=(rnd()%n)+1,r=(rnd()%n)+1;
if(l>r)swap(l,r);
if(op==3)x=(rnd()%(r-l+1))+1;
else x=(rnd()%vmax)+1;
if(op==4)y=(rnd()%vmax)+1;
if(op<2)add(l,r,(LL)x);
else if(op<3)assign(l,r,(LL)x);
else if(op<4)printf("%lld\n",ask_k(l,r,x));
else printf("%lld\n",mi_sum(l,r,x,y));
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#include<vector>
#include<set>
#define Re register int
#define IT set<QAQ>::iterator
using namespace std;
const int N=1e5+5;
struct QAQ{
int l,r;mutable int v;
QAQ(Re L,Re R=-1,Re V=0):l(L),r(R),v(V){}
bool operator<(QAQ o)const{return l<o.l;}
};
int x,y,n,m,fu,op;set<QAQ>s;
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
if(fu)x=-x;
}
inline IT split(Re w){
IT it=s.lower_bound(QAQ(w));
if(it!=s.end()&&it->l==w)return it;
--it;
Re L=it->l,R=it->r,V=it->v;
s.erase(it);
s.insert(QAQ(L,w-1,V));
return s.insert(QAQ(w,R,V)).first;
}
inline void assign(Re l,Re r,Re v){
IT itr=split(r+1),itl=split(l);
s.erase(itl,itr),s.insert(QAQ(l,r,v));
}
inline int count1(Re l,Re r){
IT itr=split(r+1),itl=split(l);Re ans=0;
while(itl!=itr)ans+=itl->v*(itl->r-itl->l+1),++itl;
return ans;
}
inline int ask1(Re l,Re r){
IT itr=split(r+1),itl=split(l);Re tmp=0,ans=0;
while(itl!=itr){
if(itl->v)tmp+=itl->r-itl->l+1;
else ans=max(ans,tmp),tmp=0;
++itl;
}
return max(ans,tmp);
}
inline void inverse(Re l,Re r){
IT itr=split(r+1),itl=split(l);
while(itl!=itr)itl->v^=1,++itl;
}
int main(){
in(n),in(m);
for(Re i=1;i<=n;++i)in(x),s.insert(QAQ(i,i,x));
s.insert(QAQ(n+1,n+1,-1));
while(m--){
in(op),in(x),in(y);++x,++y;
if(!op)assign(x,y,0);
else if(op<2)assign(x,y,1);
else if(op<3)inverse(x,y);
else if(op<4)printf("%d\n",count1(x,y));
else printf("%d\n",ask1(x,y));
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#include<vector>
#include<set>
#define Re register int
#define IT set<QAQ>::iterator
using namespace std;
const int N=2e5+5;
struct QAQ{
int l,r;mutable int v;
QAQ(Re L,Re R=-1,Re V=0):l(L),r(R),v(V){}
bool operator<(QAQ o)const{return l<o.l;}
};
int x,y,xx,yy,n,m,fu,op;set<QAQ>s;
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
if(fu)x=-x;
}
inline IT split(Re w){
IT it=s.lower_bound(QAQ(w));
if(it!=s.end()&&it->l==w)return it;
--it;
Re L=it->l,R=it->r,V=it->v;
s.erase(it);
s.insert(QAQ(L,w-1,V));
return s.insert(QAQ(w,R,V)).first;
}
inline void assign(Re l,Re r,Re v){
IT itr=split(r+1),itl=split(l);
s.erase(itl,itr),s.insert(QAQ(l,r,v));
}
inline int ask1(Re l,Re r){
IT itr=split(r+1),itl=split(l);Re tmp=0,ans=0;
while(itl!=itr){
if(!itl->v)tmp+=itl->r-itl->l+1;
else ans=max(ans,tmp),tmp=0;
++itl;
}
return max(ans,tmp);
}
inline void scure(Re l,Re r,Re a,Re b){
IT itr=split(r+1),itl=split(l),it=itl;Re t=0;
while(it!=itr)t+=it->v*(it->r-it->l+1),++it;
s.erase(itl,itr),s.insert(QAQ(l,r,0));
if(!t)return;
itr=split(b+1),itl=split(a);
if(t>=b-a+1){s.erase(itl,itr),s.insert(QAQ(a,b,1));return;}
for(;itl!=itr;++itl)
if(!itl->v){
t-=itl->r-itl->l+1;
if(t<0){assign(itl->l,itl->r+t,1);break;}
else itl->v=1;
}
}
int main(){
in(n),in(m);
s.insert(QAQ(1,n,1));
while(m--){
in(op),in(x),in(y);
if(!op)assign(x,y,0);
else if(op<2)in(xx),in(yy),scure(x,y,xx,yy);
else printf("%d\n",ask1(x,y));
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+5;
int n,x,y,T,op,A[N];
inline void in(Re &x){
Re fu=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=fu?-x:x;
}
struct Leftist_Tree{
int fa[N],pl[N],pr[N],dis[N];
inline int merge(Re x,Re y){
if(!x||!y)return x+y;
if(A[x]>A[y]||(A[x]==A[y]&&x>y))swap(x,y);
pr[x]=merge(pr[x],y);
if(dis[pl[x]]<dis[pr[x]])swap(pl[x],pr[x]);
dis[x]=dis[pr[x]]+1;
if(pl[x])fa[pl[x]]=x;
if(pr[x])fa[pr[x]]=x;
return x;
}
inline int top(Re x){return fa[x]==x?x:fa[x]=top(fa[x]);}
inline void pop(Re x){
A[x]=-1,fa[pl[x]]=pl[x],fa[pr[x]]=pr[x];
fa[x]=merge(pl[x],pr[x]),pl[x]=pr[x]=0;
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=1;i<=n;++i)in(A[i]),T1.fa[i]=i;
while(T--){
in(op),in(x);
if(op&1){
in(y);
if(A[x]!=-1&&A[y]!=-1){
x=T1.top(x),y=T1.top(y);
if(x!=y)T1.merge(x,y);
}
}
else if(A[x]==-1)puts("-1");
else printf("%d\n",A[T1.top(x)]),T1.pop(T1.top(x));
}
}
//#pragma GCC optimize(3,"Ofast","inline")
//#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#define Re register int
using std::sort;
const int N=1e5+5,K=2e5+5;
int n,m,k,C[K],ans[N];
struct QAQ{int a,b,c,cnt,ans;}a[N],Q[N];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline bool cmp1(QAQ p,QAQ o){return p.a!=o.a?p.a<o.a:(p.b!=o.b?p.b<o.b:p.c<o.c);}
inline bool cmp2(QAQ p,QAQ o){return p.b<o.b;}
inline void add(Re x,Re v){while(x<=k)C[x]+=v,x+=x&-x;}
inline int ask(Re x){
Re ans=0;
while(x)ans+=C[x],x-=x&-x;
return ans;
}
inline void CDQ(Re L,Re R){
if(L==R)return;
Re mid=L+R>>1;
CDQ(L,mid),CDQ(mid+1,R);
sort(Q+L,Q+mid+1,cmp2),sort(Q+mid+1,Q+R+1,cmp2);
Re j=L;
for(Re i=mid+1;i<=R;++i){
while(j<=mid&&Q[j].b<=Q[i].b)add(Q[j].c,Q[j].cnt),++j;
Q[i].ans+=ask(Q[i].c);
}
for(Re i=L;i<j;++i)add(Q[i].c,-Q[i].cnt);
}
int main(){
in(n),in(k);
for(Re i=1;i<=n;++i)in(a[i].a),in(a[i].b),in(a[i].c);
sort(a+1,a+n+1,cmp1);
for(Re i=1;i<=n;++i){
if(i>2&&a[i].a==a[i-1].a&&a[i].b==a[i-1].b&&a[i].c==a[i-1].c)++Q[m].cnt;
else Q[++m]=a[i],Q[m].cnt=1;
}
CDQ(1,m);
for(Re i=1;i<=m;++i)ans[Q[i].ans+Q[i].cnt-1]+=Q[i].cnt;
for(Re i=0;i<n;++i)printf("%d\n",ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=5e4+3,M=5e4+3,inf=1e9;
int n,x,T,Ans[M];
struct QAQ{int l,r,op,id;LL k;}Q[N+M],Q1[N+M],Q2[N+M];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Segment_Tree{
#define pl p<<1
#define pr p<<1|1
#define Mid (L+R>>1)
struct QAQ{int CL,add;LL S;}tr[N<<2];
inline void pushup(Re p){tr[p].S=tr[pl].S+tr[pr].S;}
inline void updata(Re p,Re L,Re R,Re v){tr[p].S+=v*(R-L+1),tr[p].add+=v;}
inline void updata_(Re p){tr[p].add=tr[p].S=0,tr[p].CL=1;}
inline void pushdown(Re p,Re L,Re R){
if(tr[p].CL)updata_(pl),updata_(pr),tr[p].CL=0;
if(tr[p].add)updata(pl,L,Mid,tr[p].add),updata(pr,Mid+1,R,tr[p].add),tr[p].add=0;
}
inline void change(Re p,Re L,Re R,Re l,Re r,Re v){
if(l<=L&&R<=r){updata(p,L,R,v);return;}
pushdown(p,L,R);
if(l<=Mid)change(pl,L,Mid,l,r,v);
if(r>Mid)change(pr,Mid+1,R,l,r,v);
pushup(p);
}
inline LL ask(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return tr[p].S;
LL ans=0;pushdown(p,L,R);
if(l<=Mid)ans+=ask(pl,L,Mid,l,r);
if(r>Mid)ans+=ask(pr,Mid+1,R,l,r);
return ans;
}
}T1;
inline void sakura(Re l,Re r,Re L,Re R){
if(L>R)return;
if(l==r){
for(Re i=L;i<=R;++i)if(Q[i].op>1)Ans[Q[i].id]=l;
return;
}
Re mid=l+r>>1,m1=0,m2=0;
for(Re i=L;i<=R;++i)
if(Q[i].op&1){
if(Q[i].k<=mid)Q1[++m1]=Q[i];
else Q2[++m2]=Q[i],T1.change(1,1,n,Q[i].l,Q[i].r,1);
}
else{
LL tmp=T1.ask(1,1,n,Q[i].l,Q[i].r);
if(Q[i].k<=tmp)Q2[++m2]=Q[i];
else Q[i].k-=tmp,Q1[++m1]=Q[i];
}
T1.updata_(1);
for(Re i=1;i<=m1;++i)Q[L+i-1]=Q1[i];
for(Re i=1;i<=m2;++i)Q[L+m1+i-1]=Q2[i];
sakura(l,mid,L,L+m1-1);
sakura(mid+1,r,L+m1,R);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=1;i<=T;++i){
in(Q[i].op),in(Q[i].l),in(Q[i].r),in(x),Q[i].k=x;
if(Q[i].op>1)Q[i].id=++Ans[0];
}
sakura(-n,n,1,T);
for(Re i=1;i<=Ans[0];++i)printf("%d\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=1e5+3,M=1e5+3,inf=1e9;
int n,x,y,z,T,cnt,a[N],Ans[M];char op;
struct QAQ{int l,r,k,op,id;}Q[N+M*2],Q1[N+M*2],Q2[N+M*2];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct BIT{
int C[N];
inline void add(Re x,Re v){while(x<=n)C[x]+=v,x+=x&-x;}
inline int ask_(Re x){Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
inline int ask(Re l,Re r){return ask_(r)-ask_(l-1);}
}T1;
inline void sakura(Re l,Re r,Re L,Re R){
if(L>R)return;
if(l==r){
for(Re i=L;i<=R;++i)if(Q[i].op>1)Ans[Q[i].id]=l;
return;
}
Re mid=l+r>>1,m1=0,m2=0;
for(Re i=L;i<=R;++i)
if(Q[i].op&1){
if(Q[i].l<=mid)Q1[++m1]=Q[i],T1.add(Q[i].id,Q[i].r);
else Q2[++m2]=Q[i];
}
else{
Re tmp=T1.ask(Q[i].l,Q[i].r);
if(Q[i].k<=tmp)Q1[++m1]=Q[i];
else Q[i].k-=tmp,Q2[++m2]=Q[i];
}
for(Re i=1;i<=m1;++i)if(Q1[i].op&1)T1.add(Q1[i].id,-Q1[i].r);
for(Re i=1;i<=m1;++i)Q[L+i-1]=Q1[i];
for(Re i=1;i<=m2;++i)Q[L+m1+i-1]=Q2[i];
sakura(l,mid,L,L+m1-1);
sakura(mid+1,r,L+m1,R);
}
int main(){
freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=1;i<=n;++i)in(a[i]),Q[++cnt]=(QAQ){a[i],1,0,1,i};
while(T--){
scanf(" %c",&op),in(x),in(y);
if(op=='C')Q[++cnt]=(QAQ){a[x],-1,0,1,x},Q[++cnt]=(QAQ){a[x]=y,1,0,1,x};
else in(z),Q[++cnt]=(QAQ){x,y,z,2,++Ans[0]};
}
sakura(-inf,inf,1,cnt);
for(Re i=1;i<=Ans[0];++i)printf("%d\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=2e5+3,M=2e5+3,inf=1e9;
int n,x,y,z,T,cnt,Ans[M];char op;
struct QAQ{int l,r,k,op,id;}Q[N+M],Q1[N+M],Q2[N+M];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct BIT{
int C[N];
inline void add(Re x,Re v){while(x<=n)C[x]+=v,x+=x&-x;}
inline int ask_(Re x){Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
inline int ask(Re l,Re r){return ask_(r)-ask_(l-1);}
}T1;
inline void sakura(Re l,Re r,Re L,Re R){
if(L>R)return;
if(l==r){
for(Re i=L;i<=R;++i)if(Q[i].op>1)Ans[Q[i].id]=l;
return;
}
Re mid=l+r>>1,m1=0,m2=0;
for(Re i=L;i<=R;++i)
if(Q[i].op&1){
if(Q[i].k<=mid)Q1[++m1]=Q[i],T1.add(Q[i].id,1);
else Q2[++m2]=Q[i];
}
else{
Re tmp=T1.ask(Q[i].l,Q[i].r);
if(Q[i].k<=tmp)Q1[++m1]=Q[i];
else Q[i].k-=tmp,Q2[++m2]=Q[i];
}
for(Re i=1;i<=m1;++i)if(Q1[i].op&1)T1.add(Q1[i].id,-1);
for(Re i=1;i<=m1;++i)Q[L+i-1]=Q1[i];
for(Re i=1;i<=m2;++i)Q[L+m1+i-1]=Q2[i];
sakura(l,mid,L,L+m1-1);
sakura(mid+1,r,L+m1,R);
}
int main(){
freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=1;i<=n;++i)in(x),Q[++cnt]=(QAQ){0,0,x,1,i};
for(Re i=1;i<=T;++i)in(x),in(y),in(z),Q[++cnt]=(QAQ){x,y,z,2,i};
sakura(-inf,inf,1,cnt);
for(Re i=1;i<=T;++i)printf("%d\n",Ans[i]);
}
// 左偏树(可并堆)模板
struct LeftistTree {
struct Node {
int value; // 节点值
int left; // 左子节点
int right; // 右子节点
int dist; // 距离(npl,空节点为0,叶节点为1)
};
vector<Node> heap; // 堆节点数组,0号节点为空节点
// 构造函数,初始化空节点
LeftistTree(int reserveSize = 0) {
heap.reserve(reserveSize + 1);
heap.push_back({0, 0, 0, 0}); // 0号节点作为空节点
}
// 创建新节点
int newNode(int value) {
heap.push_back({value, 0, 0, 1});
return (int)heap.size() - 1;
}
// 比较优先级,返回a是否优先于b
// 可根据需要重写(此处为示例:值大的优先)
bool higherPriority(int a, int b) {
if (b == 0) return true; // b为空
if (a == 0) return false; // a为空
return heap[a].value > heap[b].value; // 大根堆
}
// 合并两个堆,返回合并后的根节点
int merge(int a, int b) {
if (a == 0) return b;
if (b == 0) return a;
// 确保a的优先级更高
if (!higherPriority(a, b)) swap(a, b);
// 递归合并右子树
heap[a].right = merge(heap[a].right, b);
// 维护左偏性质:左子树dist >= 右子树dist
if (heap[heap[a].left].dist < heap[heap[a].right].dist) {
swap(heap[a].left, heap[a].right);
}
// 更新dist
heap[a].dist = heap[heap[a].right].dist + 1;
return a;
}
// 弹出堆顶(删除根节点)
int pop(int root) {
return merge(heap[root].left, heap[root].right);
}
// 获取堆顶值
int top(int root) {
return heap[root].value;
}
// 判断堆是否为空
bool empty(int root) {
return root == 0;
}
};typedef pair<int,int> P; // 存储键值对,通常用于比较优先级
struct Node {
int l, r, d; // l:左孩子, r:右孩子, d:距离(null路径长度)
P v; // 存储的值(键值对)
Node(){}
Node(int _l,int _r,int _d,P _v){l=_l,r=_r,d=_d,v=_v;}
} T[N]; // 数组存储所有节点
int merge(int a,int b){
if(!a) return b;
if(!b) return a;
if(T[a].v < T[b].v)swap(a,b);
T[a].r = merge(T[a].r,b);
if(T[T[a].l].d < T[T[a].r].d)swap(T[a].l,T[a].r);
T[a].d=T[a].r ? T[T[a].r].d+1:0;
return a;
}
int pop(int a){
int l = T[a].l,r=T[a].r;
T[a].l=T[a].r=T[a].d=0;
return merge(l,r);
}