新手学习网站建设,网站建设开拓该行业的难点疑,办公室装修图片大全,免费开源网店系统有哪些打的big出了点小问题#xff0c;maxx初值我设的0然后少了10分 第二题暴力打炸 第一题剪了一些没用的枝依然40分 总分70 这是一次失败的考试 string 想到和序列那个题很像#xff0c;但我没做序列#xff0c;考场回忆学长讲课#xff0c;打不出来。最后我口胡了一个CDQ分治maxx初值我设的0然后少了10分 第二题暴力打炸 第一题剪了一些没用的枝依然40分 总分70 这是一次失败的考试 string 想到和序列那个题很像但我没做序列考场回忆学长讲课打不出来。最后我口胡了一个CDQ分治大概能减很多枝比如之前5 6 修改之后4 6修改那么其实你5 6不用改。 秉承这个思路我随意打了一个分治然后依然40分。 题解 我们可以维护每一段区间字母个数维护一个桶每次询问先把桶求出来按照顺序排序时我们可以顺序枚举26个字母进行区间修改然后按照逆序反过来枚举就好了。这样把修改操作转化为若干个区间修改。但单单这么做我们会T维护起来也不好维护各种懒标记很恶心我们还需要别的特殊姿势 if(tr[p].a) tr[p1].atr[p].a,tr[p1|1].atr[p].a; 这样做我们修改和询问就不用递归到儿子节点了而且这样我们还节省了维护懒标记时间 那么我们思考如何维护 修改时 if(tr[p].lltr[p].rr||tr[p].ax){tr[p].ax;return ;} 若区间不完全覆盖 if(tr[p].a) tr[p1].atr[p].a,tr[p1|1].atr[p].a,tr[p].a0; 代码 #includebits/stdc.h
using namespace std;
#define ll long long
#define A 1010101
struct tree{ll x,f,a,l,r;
}tr[A];
char s[A];
ll w[A];
ll n,m;
mapll,charmp;
void built(ll p,ll l,ll r){tr[p].ll,tr[p].rr;if(lr){
// printf(l%lld s%lld\n,l,s[l]-a1ll);tr[p].as[l]-a1;return ;}ll mid(lr)1;built(p1,l,mid);built(p1|1,mid1,r);if(tr[p1].atr[p1|1].a)tr[p].atr[p1].a;
}
void getsum(ll p,ll l,ll r){
// printf(l%lld r%lld l%lld r%lld tr[p].a%lld\n,tr[p].l,tr[p].r,l,r,tr[p].a);if(tr[p].lltr[p].rrtr[p].a){w[tr[p].a](tr[p].r-tr[p].l1);return ;}ll mid(tr[p].ltr[p].r)1;if(tr[p].a) tr[p1].atr[p].a,tr[p1|1].atr[p].a;if(midl)getsum(p1,l,r);if(midr)getsum(p1|1,l,r);
}
void change(ll p,ll l,ll r,ll x){
// printf(l%lld r%lld ***\n,l,r);if(tr[p].lltr[p].rr||tr[p].ax){tr[p].ax;return ;}ll mid(tr[p].ltr[p].r)1;
// printf(tr[%lld]%lld\n,p,tr[p].a); if(tr[p].a) tr[p1].atr[p].a,tr[p1|1].atr[p].a,tr[p].a0;if(midl) change(p1,l,r,x);if(midr) change(p1|1,l,r,x);
}
void out(ll p){
// printf(p%lld tr[p].a%lld mp%c\n,p,tr[p].a,mp[tr[p].a]);if(tr[p].a){for(ll i1;itr[p].r-tr[p].l1;i)printf(%c,(char)mp[tr[p].a]);return ;}out(p1);out(p1|1);
}
void pre(){for(ll i1;i26;i)mp[i]ai-1;return ;
}
int main(){pre();scanf(%lld%lld,n,m);scanf(%s,s1);built(1,1,n);for(ll i1,a,b,c,t;im;i){scanf(%lld%lld%lld,a,b,c); getsum(1,a,b);ll la;if(c){for(ll t1;t26;t)if(w[t])change(1,l,lw[t]-1,t),llw[t],w[t]0;}else {for(ll t26;t1;t--)if(w[t])change(1,l,lw[t]-1,t),llw[t],w[t]0;}}out(1);puts();
} big 题解 $40\%$ 按照题目说的做,直接枚举 $100\%$ 我们建一棵tire树, 代码 #includebits/stdc.h
#define ll long long
#define A 6000000
using namespace std;
ll tire[A][2],t[A],sum[A],dl[A],a[A];
ll tot1,n,m,maxx0,ans0;
bool pan;
ll change(ll x){return (2*x/(1n)2*x)%(1n);
}
bool cmp(ll x,ll y){return xy;
}
inline void insert(ll x)
{ll p1;for(ll i1;in;i){ll zan(x(n-i))1;
// printf(zan%lld tot%lld\n,zan,tot);if(!tire[p][zan]) tire[p][zan]tot;ptire[p][zan];}
}
inline ll dfs(ll x,ll zhi,ll deep)
{if(deep0){dl[dl[0]]zhi;}
// printf(trie[0][1][%lld][%lld] deep%lld zhi%lld 1%lld\n,tire[x][0],tire[x][1],deep,zhi,1lldeep);if(tire[x][0]!tire[x][1])dfs(tire[x][0],zhi^(1lldeep),deep-1);if(!tire[x][0]tire[x][1])dfs(tire[x][1],zhi^(1lldeep),deep-1);if(tire[x][0]tire[x][1]){dfs(tire[x][0],zhi,deep-1);dfs(tire[x][1],zhi,deep-1);}
}
int main()
{scanf(%lld%lld,n,m);for(ll i1;im;i)scanf(%lld,a[i]);for(ll im;i1;i--)sum[i]sum[i1]^a[i];for(ll i0,now0;im;i){
// printf(now%lld add%lld\n,now,now^sum[i1]);nownow^change(a[i]);insert(now^sum[i1]);}
// printf(1 %lld 0%lld\n,tire[1][1],tire[1][0]);dfs(1,0,n-1);sort(dl1,dldl[0]1,cmp);for(ll i1;idl[0];i)if(dl[i]dl[1]) ans;printf(%lld\n%lld\n,dl[1],ans);
} 转载于:https://www.cnblogs.com/znsbc-13/p/11286426.html
