crz_qwq @ 2024-08-02 19:27:39
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=32;
struct balanced_tree{
int trie[N*M][2],sz[N*M],tot=0;
void init()
{
memset(trie,0,sizeof trie);
memset(sz,0,sizeof sz);
}
bool find(int x)
{
int p=0;
for(int i=M-1;i>=0;--i)
{
int k=(x>>i)&1;
if(!trie[p][k])
return 0;
p=trie[p][k];
}
return 1;
}
void insert(int x)
{
int p=0;
for(int i=M-1;i>=0;--i)
{
int k=(x>>i)&1;
if(!trie[p][k])
trie[p][k]=++tot;
p=trie[p][k];
++sz[p];
}
}
void erase(int x)
{
if(!find(x))
return ;
int p=0;
for(int i=M-1;i>=0;--i)
{
int k=(x>>i)&1;
p=trie[p][k];
--sz[p];
}
}
int rank(int x)
{
int p=0,res=0;
for(int i=M-1;i>=0;--i)
{
int k=(x>>i)&1;
if(k)
res+=sz[trie[p][0]];
p=trie[p][k];
if(!p)
break;
}
return res;
}
int kth(int x)
{
int p=0,res=0;
for(int i=M-1;i>=0;--i)
{
if(sz[trie[p][0]]>=x)
p=trie[p][0];
else
{
x-=sz[trie[p][0]];
res+=(1<<i);
p=trie[p][1];
}
}
return res;
}
int pre(int x){return kth(rank(x));}
int nxt(int x){return kth(rank(x+1)+1);}
}tr;
int a[N];
int query_rank(int p,int pl,int pr,int L,int R,int k)
{
if(R<pl||pr<L)
return 0;
if(L<=pl&&pr<=R)
{
for(int i=pl;i<=pr;++i)
tr.insert(a[i]);
int ans=tr.rank(k);
for(int i=pl;i<=pr;++i)
tr.erase(a[i]);
return ans;
}
int mid=(pl+pr)>>1;
return query_rank(p<<1,pl,mid,L,R,k)+query_rank(p<<1|1,mid+1,pr,L,R,k);
}
int query_kth(int p,int pl,int pr,int L,int R,int k)
{
int l=-1,r=1e9+1;
while(l+1<r)
{
int mid=(l+r)>>1;
if(query_rank(p,pl,pr,L,R,mid)<k)
l=mid;
else
r=mid;
}
return l;
}
void update(int p,int d){a[p]=d;}
int query_pre(int p,int pl,int pr,int L,int R,int k)
{
if(R<pl||pr<L)
return -2147483647;
if(L<=pl&&pr<=R)
{
for(int i=pl;i<=pr;++i)
tr.insert(a[i]);
int ans=tr.pre(k);
for(int i=pl;i<=pr;++i)
tr.erase(a[i]);
return ans;
}
int mid=(pl+pr)>>1;
return max(query_pre(p<<1,pl,mid,L,R,k),query_pre(p<<1|1,mid+1,pr,L,R,k));
}
int query_nxt(int p,int pl,int pr,int L,int R,int k)
{
if(R<pl||pr<L)
return 2147483647;
if(L<=pl&&pr<=R)
{
for(int i=pl;i<=pr;++i)
tr.insert(a[i]);
int ans=tr.nxt(k);
for(int i=pl;i<=pr;++i)
tr.erase(a[i]);
return ans;
}
int mid=(pl+pr)<<1;
return min(query_nxt(p<<1,pl,mid,L,R,k),query_nxt(p<<1|1,mid+1,pr,L,R,k));
}
int query(int p,int pl,int pr,int L,int R)
{
if(R<pl||pr<L)
return 0;
if(L<=pl&&pr<=R)
{
int res=0;
for(int i=pl;i<=pr;++i)
res+=a[i];
return res;
}
int mid=(pl+pr)>>1;
return query(p<<1,pl,mid,L,R)+query(p<<1|1,mid+1,pr,L,R);
}
signed main()
{
int x,y;
cin>>x>>y;
update(1,x);
update(2,y);
cout<<query_rank(1,1,2,1,1,2)*query_kth(1,1,2,1,1,2)*query_nxt(1,1,2,1,1,2)*query_pre(1,1,2,2,1,2)*1+query(1,1,2,1,2);
}by _ChongYun_ @ 2024-08-02 19:38:54
不如可持久化线段树。
by wanghonghui @ 2024-08-02 19:40:38
@crz_qwq 你是想写高精度但没写对是吧。
死循环了。
再说这题不用高精度。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int a[350],b[350],c[360];
int main(){
string s1,s2;
cin>>s1>>s2;
for(int i=0,j=s1.size()-1;j>=0;i++,j--)a[i]=s1[j]-'0';
for(int i=0,j=s2.size()-1;j>=0;i++,j--)b[i]=s2[j]-'0';
int len=max(s1.size(),s2.size())+1;
for(int i=0;i<len;i++){
c[i]=a[i]+b[i];
}
for(int i=0;i<len;i++){
c[i+1]+=c[i]/10;
c[i]%=10;
}
while(c[len-1]==0&&len>1)len--;
for(int i=len-1;i>=0;i--)cout<<c[i];
return 0;
}by crz_qwq @ 2024-08-02 19:41:56
@wanghonghui 你要不再看一眼我写的什么？
by wanghonghui @ 2024-08-02 19:46:17
@crz_qwq 树？
by crz_qwq @ 2024-08-02 19:48:11
@wanghonghui 有没有可能这是树套树
by wanghonghui @ 2024-08-02 19:50:37
@crz_qwq 所以说这是哪一题？
by crz_qwq @ 2024-08-02 19:52:48
@wanghonghui 这道题
by huyangmu @ 2024-08-02 20:00:46
@crz_qwq 不管你了。
by crz_qwq @ 2024-08-02 20:01:34
@huyangmu 巨佬救救蒟蒻吧
by huyangmu @ 2024-08-02 20:08:23
@crz_qwq 不如直接叫gengen队。