卡常真好玩,卡到了loj rank1(2019.1.29)
// luogu-judger-enable-o2
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef unsigned int u32;
typedef unsigned long long u64;
inline void output_arr(u32 *A, u32 size) {
u32 ret = size * sizeof(u32);
u32 x = 23333333;
const u32 * ed = A + size;
for (u32*i=A;i!=ed; ++ i){
ret^=*i+x,x^=x<<13,x^=x>>17,x^=x<<5;
}
printf("%u
", ret);
}
namespace Sorting {
int cnt0[256],cnt8[256],cnt16[256],cnt24[256];
u32 *a,*b;
inline void init_data(u32 *a, int n,u32 seed) {
const u32 * ed = a + n;
for (u32*i = a; i != ed; ++ i){
seed ^= seed << 13,seed ^= seed >> 17,seed ^= seed << 5;
*i=seed;
++cnt0[seed & 255], ++cnt8[seed >> 8 & 255],
++cnt16[seed >> 16 & 255], ++cnt24[seed >> 24];
}
for(int i=1;i<256;++i)
cnt0[i] += cnt0[i-1],
cnt8[i] += cnt8[i-1],
cnt16[i] += cnt16[i-1],
cnt24[i] += cnt24[i-1];
register u32*i;
for(i=a+n-1;i>a;i-=8){
b[--cnt0[*i&255]]=*i;
b[--cnt0[i[-1]&255]]=i[-1];
b[--cnt0[i[-2]&255]]=i[-2];
b[--cnt0[i[-3]&255]]=i[-3];
b[--cnt0[i[-4]&255]]=i[-4];
b[--cnt0[i[-5]&255]]=i[-5];
b[--cnt0[i[-6]&255]]=i[-6];
b[--cnt0[i[-7]&255]]=i[-7];
}
for(i=b+n-1;i>b;i-=8){
a[--cnt8[*i>>8&255]]=*i;
a[--cnt8[i[-1]>>8&255]]=i[-1];
a[--cnt8[i[-2]>>8&255]]=i[-2];
a[--cnt8[i[-3]>>8&255]]=i[-3];
a[--cnt8[i[-4]>>8&255]]=i[-4];
a[--cnt8[i[-5]>>8&255]]=i[-5];
a[--cnt8[i[-6]>>8&255]]=i[-6];
a[--cnt8[i[-7]>>8&255]]=i[-7];
}
for(i=a+n-1;i>a;i-=8){
b[--cnt16[*i>>16&255]]=*i;
b[--cnt16[i[-1]>>16&255]]=i[-1];
b[--cnt16[i[-2]>>16&255]]=i[-2];
b[--cnt16[i[-3]>>16&255]]=i[-3];
b[--cnt16[i[-4]>>16&255]]=i[-4];
b[--cnt16[i[-5]>>16&255]]=i[-5];
b[--cnt16[i[-6]>>16&255]]=i[-6];
b[--cnt16[i[-7]>>16&255]]=i[-7];
}
for(i=b+n-1;i>b;i-=8){
a[--cnt24[*i>>24]]=*i;
a[--cnt24[i[-1]>>24]]=i[-1];
a[--cnt24[i[-2]>>24]]=i[-2];
a[--cnt24[i[-3]>>24]]=i[-3];
a[--cnt24[i[-4]>>24]]=i[-4];
a[--cnt24[i[-5]>>24]]=i[-5];
a[--cnt24[i[-6]>>24]]=i[-6];
a[--cnt24[i[-7]>>24]]=i[-7];
}
}
int n;
inline void main() {
register u32 seed;
scanf("%d%u", &n, &seed);
a = new u32[n<<1];
b = a + n;
init_data(a, n, seed);
output_arr(a, n);
}
}
namespace Game {
int n,q;
u64 f1[64][20000];
u64 f2[64][20000];
inline void add(u64 f[64][20000],int bit){
if(bit < 64)
for(int i=0;i<=bit;++i)
*f[i]|=1ull<< bit-i;
else for(int i=0;i<64;++i)
f[i][bit-i>>6] |= 1ull << (bit-i&63);
}
inline void init(char * s1,char * s2){
for(int i=0;i<n;++i){
if(s1[i]=='0')add(f1,i*3);
if(s1[i]=='1')add(f1,i*3+1);
if(s1[i]=='2')add(f1,i*3+2);
if(s2[i]=='0')add(f2,i*3+2);
if(s2[i]=='1')add(f2,i*3);
if(s2[i]=='2')add(f2,i*3+1);
}
}
void main() {
scanf("%d%d", &n, &q);
char *s1 = new char[n + 1];
char *s2 = new char[n + 1];
scanf("%s%s", s1, s2);
init(s1,s2);
u32 *anss = new u32[q];
for (int k = 0; k < q; ++k) {
int x,y,len;
scanf("%d%d%d",&x,&y,&len);
x*=3,y*=3,len*=3;
int l = len >> 6;
u64*i=f1[x&63]+(x>>6),*j=f2[y&63]+(y>>6);
int ans=0,cnt=0;
for(;cnt+8<l;cnt+=8,i+=8,j+=8){
ans+=__builtin_popcountll(i[0]&j[0]);
ans+=__builtin_popcountll(i[1]&j[1]);
ans+=__builtin_popcountll(i[2]&j[2]);
ans+=__builtin_popcountll(i[3]&j[3]);
ans+=__builtin_popcountll(i[4]&j[4]);
ans+=__builtin_popcountll(i[5]&j[5]);
ans+=__builtin_popcountll(i[6]&j[6]);
ans+=__builtin_popcountll(i[7]&j[7]);
}
for(;cnt<l;++cnt,++i,++j) ans+=__builtin_popcountll(*i&*j);
anss[k]=ans+__builtin_popcountll(*i&*j&(1ull<<(len&63))-1);
}
output_arr(anss, q);
}
}
namespace Parentheses {
u32 f[366666*2],*id=f+366666;
u32 p[366666*2],*g=p+366666;
int cur=1;
void main() {
int n;
scanf("%d", &n);
char *s = new char[n + 1];
scanf("%s", s);
id[0]=1;
for(int i=0;i<n;++i){
if(s[i] == ')')
*id++=0;
if(s[i] == '(')
*--id=0;
if (i !=n-1 && s[i] == '?' && s[i+1] == '?'){
*--id=0,*--id=0;
id[0]=id[2]+id[4];
id[1]=id[3]*2+id[5];
const int ed=std::min(i+4,n - i + 4);
for(int j=2+(i&1);j<=ed;){
id[j] += id[j+2]*2 + id[j+4],j+=2;
id[j] += id[j+2]*2 + id[j+4],j+=2;
id[j] += id[j+2]*2 + id[j+4],j+=2;
id[j] += id[j+2]*2 + id[j+4],j+=2;
id[j] += id[j+2]*2 + id[j+4],j+=2;
id[j] += id[j+2]*2 + id[j+4],j+=2;
id[j] += id[j+2]*2 + id[j+4],j+=2;
id[j] += id[j+2]*2 + id[j+4],j+=2;
}
++i;
continue;
}
if(s[i] == '?'){
*--id=0;
const int ed=std::min(i+2,n-i+2);
for(u32 j=!(i&1);j<=ed;){
id[j]+=id[j+2],j+=2;
id[j]+=id[j+2],j+=2;
id[j]+=id[j+2],j+=2;
id[j]+=id[j+2],j+=2;
id[j]+=id[j+2],j+=2;
id[j]+=id[j+2],j+=2;
id[j]+=id[j+2],j+=2;
id[j]+=id[j+2],j+=2;
}
}
}
printf("%u
", id[0]);
}
}
int main() {
int task_id;
scanf("%d", &task_id);
switch (task_id) {
case 1:
Sorting::main();
break;
case 2:
Game::main();
break;
case 3:
Parentheses::main();
break;
}
return 0;
}