太原网站建设制作,微信网站怎么开发,济源建设企业网站公司,商务网站创建方案我们观察数据#xff1a;树套树 PASS 主席树 PASS 一层一个Trie PASS 再看#xff0c;异或#xff01;我们就把目光暂时定在01Tire然后我们发现#xff0c;我们可以带着一堆点在01Trie上行走#xff0c;因为O(n*q*30m*30)是一个可选复杂度。 我们想一下我们正常的时候…我们观察数据树套树 PASS 主席树 PASS 一层一个Trie PASS 再看异或我们就把目光暂时定在01Tire然后我们发现我们可以带着一堆点在01Trie上行走因为O(n*q*30m*30)是一个可选复杂度。 我们想一下我们正常的时候的01Trie其实是通过在每一层比较大小来确定这一为是0还是1所以我们从上到下一位一位地走统计每在这一位异或值为1的数的个数如果这一位是一的个数大于k那么我们就使这一位为1那么我们就舍弃这一位为0的状态就是所有的点都走变为1的路如果这一位是一的个数小于k那么我们就使这一位为0其余同理。 #include cstdio
using namespace std;
const int A30,MAXN12000000,N1010,M300010;
inline void read(int sum){register char chgetchar();for(sum0;ch0||ch9;chgetchar());for(;ch0ch9;sum(sum1)(sum3)ch-0,chgetchar());
}
struct Trie{Trie *ch[2];int size;
}*root[M],*null,node[MAXN],*now[N][2];
int n,m,sz1,a[N];
int main(){nullnode,null-ch[0]null-ch[1]null,root[0]null;read(n),read(m);for(register int i1;in;i)read(a[i]);for(register int i1,x;im;i){read(x),root[i]nodesz,sz;register Trie *proot[i],*lastroot[i-1];for(register int iA;i0;i--)p-ch[(xi)1]nodesz,sz,p-ch[((xi)1)^1]last-ch[((xi)1)^1],pp-ch[(xi)1],lastlast-ch[(xi)1],p-sizelast-size1;}register int u,d,l,r,k,Q;read(Q);while(Q--){read(u),read(d),read(l),read(r),read(k);register int ret0;for(register int iu;id;i)now[i][1]root[r],now[i][0]root[l-1];for(register int iA,sum0;i0;i--,sum0){for(register int ju;jd;j)sum((a[j]i)1)0?(now[j][1]-ch[1]-size-now[j][0]-ch[1]-size):(now[j][1]-ch[0]-size-now[j][0]-ch[0]-size);if(sumk){ret|1i;for(register int ju;jd;j)now[j][1]now[j][1]-ch[((a[j]i)1)^1],now[j][0]now[j][0]-ch[((a[j]i)1)^1];}else{k-sum;for(register int ju;jd;j)now[j][1]now[j][1]-ch[(a[j]i)1],now[j][0]now[j][0]-ch[(a[j]i)1];}}printf(%d\n,ret);}return 0;
} 转载于:https://www.cnblogs.com/TSHugh/p/7281862.html
