题解不按顺序给出

目录：

• ycz的妹子

• lty loves 96!

• mzf的考验

• hby与tkw的基情

• 抓住czx

ycz的妹子

题目背景：

\(ycz\)有很多很多的妹子（\(ycz\)：瞎说）

题目描述：

机房神犇\(ycz\)有n个青梅竹马，她们分别住在1~n号城市中。小时候的她们美丽可爱，但是由于女大十八变，有些妹子的颜值发生了变化，但是十分重感情的\(ycz\)神犇不忍心抛弃她们，于是记录下来了她们颜值变化的值，我们用\(C\, x\, y\)表示第\(x\)个城市的妹子的颜值下降了\(y\)（\(y\)有可能是负数）。长大之后的\(ycz\)非常有魅力，有许多妹子被\(ycz\)迷得神魂颠倒，我们用\(I\, x\, y\)表示第\(x\)个城市有一个妹子喜欢上了\(ycz\)，她的颜值为\(y\)（\(y\)有可能是负数，但是\(ycz\)来者不拒）。但在中途有一些妹子和\(ycz\)吵架了，于是就分手了，我们用\(D\, x\)表示第\(x\)个妹子和\(ycz\)分手了。

最近神犇\(ycz\)要去全国各地找他的妹子们，为了方便计算，我们珂以把\(ycz\)的妹子所在的城市当作是一条直线，并且挨在一起。神犇\(ycz\)由于忙于和他的妹子们联系此时已经很累了，于是交给你一个这样的任务：他想知道他在某个时间去找他的所有妹子们珂以获得多大的愉悦度，这个愉悦度为他找的妹子的颜值数，你要做的就是求出这个愉悦度之和（注意长大后妹子们的颜值可能为负数/滑稽）。

注意：每个城市只允许有一个妹子，也就是说后来喜欢上\(ycz\)的妹子会赶走之前这个城市喜欢\(ycz\)的妹子（一城不容二女）。

输入格式：

第一行两个正整数\(n\)和\(m\) \((1<=n<=100000)\)

第二行为\(n\)个整数\(a_i\)，表示小时候\(ycz\)的青梅竹马的颜值\((1<=a_i<=10^9)\)

接下来\(m\)行，每行为一条信息，每条信息可能是下面的一种:

\(C\, x\, y\)表示第\(x\)个城市的妹子的颜值下降了\(y\)

\(I\, x\, y\)表示在第\(x\)个城市有一个颜值为\(y\)的妹子迷上了\(ycz\)

\(D\, x\)表示第\(x\)个妹子和\(ycz\)分手了

\(Q\)表示\(ycz\)现在想知道如果现在去找他所有的妹子们珂以获得多大的愉悦度

说明：妹子们居住的城市编号最大为\(5\times 10^5\)

输出格式：

对于每一个\(Q\)输出一个整数

样例输入：

5 101 2 3 4 5QC 3 2QI 6 6QD 4QC 4 2I 7 9Q

样例输出：

1513191522

提示与说明：

对于30%的数据\(1<=n,m<=10\)

对于70%的数据\(1<=n,m<=1000\)

对于100%的数据\(1<=n,m<=100000,1<=a_i,y<=10^9\)

题解：

30分：我也不知道怎么拿啊...(暴力分xiajb给的)

70分：直接暴力就好了...

code:

/*Program from Luvwgyx*/#include
    
     #include
     
      #include
      
       using namespace std;const int maxn=100010;int n,m,a[maxn];char s[10];int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}int main(){    n=read();m=read();    for(int i=1;i<=n;i++)a[i]=read();    for(int i=1;i<=m;i++){        scanf("%s",s+1);        if(s[1]=='C'){            int x=read(),y=read();            a[x]-=y;        }        if(s[1]=='I'){            int x=read(),y=read();            a[x]=y;        }        if(s[1]=='D'){            int cnt=0,pos,x=read();            for(int i=1;i<=maxn-10;i++)                if(a[i]){cnt++;if(cnt==x){pos=i;break;}}            a[pos]=0;        }        if(s[1]=='Q'){            int ans=0;            for(int i=1;i<=maxn-10;i++)                ans+=a[i];            printf("%d\n",ans);        }    }    return 0;}
      
     
    

100分：

线段树中存颜值和以及妹子的数量就好了，具体的代码去看。

PS：应Wolfycz墙裂要求，此处贴上他的代码（好丑啊）我代码在下面，泥萌觉得哪个好看就看哪个吧QAQ

code:

/*program from Wolfycz*/#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define inf 0x7f7f7f7fusing namespace std;typedef long long ll;typedef unsigned int ui;typedef unsigned long long ull;inline int read(){    int x=0,f=1;char ch=getchar();    for (;ch<'0'||ch>'9';ch=getchar())  if (ch=='-')    f=-1;    for (;ch>='0'&&ch<='9';ch=getchar())    x=(x<<1)+(x<<3)+ch-'0';    return x*f;}inline void print(int x){    if (x>=10)  print(x/10);    putchar(x%10+'0');}const int N=1e5;int val[(N<<1)+10];struct Segment{    #define ls (p<<1)    #define rs (p<<1|1)    struct node{        int cnt;ll sum;        void insert(int _sum,int _cnt){sum=_sum,cnt=_cnt;}        node(){sum=cnt=0;}    }tree[(N<<3)+10];    friend node operator +(const node &x,const node &y){        node z;        z.sum=x.sum+y.sum;        z.cnt=x.cnt+y.cnt;        return z;    }    void build(int p,int l,int r){        if (l==r){            tree[p].insert(val[l],(bool)val[l]);            return;        }        int mid=(l+r)>>1;        build(ls,l,mid),build(rs,mid+1,r);        tree[p]=tree[ls]+tree[rs];    }    void change(int p,int l,int r,int x,int v){        if (l==r){            tree[p].insert(v,1);            return;        }        int mid=(l+r)>>1;        if (x<=mid) change(ls,l,mid,x,v);        else    change(rs,mid+1,r,x,v);        tree[p]=tree[ls]+tree[rs];    }    void insert(int p,int l,int r,int x,int v){        if (l==r){            tree[p].sum-=v;            return;        }        int mid=(l+r)>>1;        if (x<=mid) insert(ls,l,mid,x,v);        else    insert(rs,mid+1,r,x,v);        tree[p]=tree[ls]+tree[rs];    }    void Delete(int p,int l,int r,int x){        if (l==r){            tree[p].insert(0,0);            return;        }        int mid=(l+r)>>1;        if (x<=tree[ls].cnt)    Delete(ls,l,mid,x);        else    Delete(rs,mid+1,r,x-tree[ls].cnt);        tree[p]=tree[ls]+tree[rs];    }}Tree;char s[2];int main(){    int n=read(),m=read();    for (int i=1;i<=n;i++)  val[i]=read();    Tree.build(1,1,N<<1);    for (int i=1;i<=m;i++){        scanf("%s",s);        if (s[0]=='C'){            int x=read(),y=read();            Tree.insert(1,1,N<<1,x,y);        }        if (s[0]=='I'){            int x=read(),y=read();            Tree.change(1,1,N<<1,x,y);        }        if (s[0]=='D'){            int x=read();            Tree.Delete(1,1,N<<1,x);        }        if (s[0]=='Q')  printf("%lld\n",Tree.tree[1].sum);    }    return 0;}
        
       
      
     
    

/*Program from Luvwgyx*/#include
    
     #include
     
      #include
      
       using namespace std;typedef long long ll;const ll maxn=2e5+10;ll n,m,a[maxn];char s[10];struct node{ll cnt,sum;}tree[maxn<<2];ll read(){    ll x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}void update(ll k){    tree[k].cnt=tree[k<<1].cnt+tree[k<<1|1].cnt;    tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;    return;}void build(ll k,ll l,ll r){    if(l==r){        tree[k].sum=a[l];        if(a[l]!=0)tree[k].cnt++;        return ;    }    ll mid=(l+r)>>1;    build(k<<1,l,mid);    build(k<<1|1,mid+1,r);    update(k);}void change(ll k,ll l,ll r,ll x,ll y){    if(l==r){tree[k].sum-=y;/*prllf("\n%d\n",l);*/return ;}    ll mid=(l+r)>>1;    if(x<=mid)change(k<<1,l,mid,x,y);    else change(k<<1|1,mid+1,r,x,y);    update(k);}void add(ll k,ll l,ll r,ll x,ll y){    if(l==r){tree[k].sum=y;tree[k].cnt=1;/*prllf("\n%d\n",l);*/return ;}    ll mid=(l+r)>>1;    if(x<=mid)add(k<<1,l,mid,x,y);    else add(k<<1|1,mid+1,r,x,y);    update(k);}void del(ll k,ll l,ll r,ll x){    if(l>r)return ;//prllf("%d %d\n",l,r);    if(l==r&&x==tree[k].cnt){tree[k].sum=0;tree[k].cnt--;return ;}    ll mid=(l+r)>>1;//prllf("%d\n",tree[k<<1].cnt);    if(x<=tree[k<<1].cnt)del(k<<1,l,mid,x);    else del(k<<1|1,mid+1,r,x-tree[k<<1].cnt);    update(k);}/*void dfs(ll k,ll l,ll r){    if(l==r){if(tree[k].sum!=0)prllf("%d:%d ",l,tree[k].sum);return ;}    ll mid=(l+r)>>1;    dfs(k<<1,l,mid);dfs(k<<1|1,mid+1,r);}*/int main(){    //freopen("girl10.in","r",stdin);    //freopen("girl10.out","w",stdout);    n=read();m=read();    for(ll i=1;i<=n;i++)a[i]=read();    build(1,1,maxn-10);    while(m--){        scanf("%s",s);        if(s[0]=='C'){ll x=read(),y=read();change(1,1,maxn-10,x,y);}        if(s[0]=='I'){ll x=read(),y=read();add(1,1,maxn-10,x,y);}        if(s[0]=='D'){ll x=read();del(1,1,maxn-10,x);}        if(s[0]=='Q')printf("%lld\n",tree[1].sum);        //dfs(1,1,maxn-10);puts("");    }    return 0;}/*2 1118 4C 2 -1C 1 0I 19 -17I 8 -1D 3I 19 12QD 1C 2 -2D 2Q*/
      
     
    

lty loves 96！

题目背景：

众所周知，\(lty\)非常喜欢\(96\)这两个数字（想歪的现在马上面壁去），更甚于复读（人本复）！

题目描述：

由于爱屋及乌，因此，\(lty\)对于那些含有\(96\)的数也非常喜欢，而这里的含有不是一般的含有，而是具有以下性质的含有（三条都需要满足）：

• 这个数为一个\(N\)位数，且没有前置零
• 这个数中至少要出现\(M\)次\(9\)和\(6\)（例：\(986996\)中出现了\(5\)次，\(9\)出现了\(3\)次，\(6\)出现了\(2\)次，共计\(5\)次）
• 这个数存在任意连续的三位\(A\),\(B\),\(C\)，满足下面任意一条
  • \(A+B+C\)为\(9\)或\(6\)
  • \((A^2+B^2)\)%\(C\)为\(9\)或\(6\)，如果\(C\)为\(0\)，则该条件视为不满足

输入格式：

一行，两个数\(N\),\(M\)。

输出格式：

一个数，表示这样的数的个数。

样例输入：

3 1

样例输出：

452

提示与说明：

对于10%的数据，\(N<=6\)，

对于40%的数据，\(N<=18\)，

对于100%的数据，\(N<=50\)，\(0<=M<=N\)。

题解：

很简单的一道数位dp。

记录\(f[i][a][b][j][k](a,b\leq 9;i,j\leq N;k=0\ or\ 1)\)，表示一个\(i\)位数，第\(i\)位和第\(i-1\)位分别为\(a,b\)，这个数中有\(j\)个6和9，这个数是否出现过题目中描述的两个条件，有则\(k=1\)，没有则\(k=0\)。

转移：

当\(a,b,c\)不满足题目中条件时：

\[ f[i][a][b][j][0]+=f[i-1][b][c][j_{last}][0],f[i][a][b][j][1]+=f[i-1][b][c][j_{last}][1] \]

否则

\[ f[i][a][b][j][1]+=f[i-1][b][c][j_{last}][0]+f[i-1][b][c][j_{last}][1] \]

\(f\)数组的类型？

如果你开\(int\)类型，你可以获得\(10\)分的好成绩。

如果你开\(long long\)类型，你可以获得\(40\)分的好成绩。

如果你开普通的未压位高精度类型，你可以获得\(0\)分的好成绩。

如果你使用任意压位高精度类型，你可以获得\(100\)分的好成绩。

emmmm，好像有\(dalao\)用\(int128\)水了\(85pts\)来着....

code:

/*Program from wym*/#include
    
     const int maxn=50;const int digit=9;const int base=1000000000;struct bignum{    int v[maxn/digit+2];    int clear(){        memset(v,0,sizeof v);        return 0;    }    int print() {        printf("%d",v[v[0]]);        for(int i=v[0]-1; i>0; --i){            int k=1;            for(int j=1; j
     
      =i))continue;                        if((i>=3)&&(((a+b+c==9)||(a+b+c==6))||((c!=0)&&(((a*a+b*b)%c==9)||((a*a+b*b)%c==6)))))                            f[i][a][b][j][1]+=f[i-1][b][c][last_j][0]+f[i-1][b][c][last_j][1];                        else {                            f[i][a][b][j][0]+=f[i-1][b][c][last_j][0];                            f[i][a][b][j][1]+=f[i-1][b][c][last_j][1];                        }                    }    ans.clear();    for(int i=1; i<=9; ++i)        for(int j=0; j<=9; ++j)            for(int k=m; k<=n; ++k)                ans+=f[n][i][j][k][1];    ans.print();    return 0;}
     
    

mzf的考验

题目背景：

\(mzf\)立志要成为一个豪杰，当然，他也是一个\(OIer\)。

他希望自己除了会\(OI\)之外还会各种东西，比如心理学、吉他、把妹等等。

为了让自己有更大的魅力，他不驼背，不熬夜，整天锻炼，双目炯炯有神，是我们机房最不像\(OIer\)的人。

然而，在与我们格格不入若干天并且将《易经》研究透彻之后，承受不住我们对他另类的言论，他爆发了。

机房在那一刹那仿佛天塌地陷，世界末日。

题目描述：

八卦有乾、坤、震、巽、坎、离、艮、兑；

两两组合，一上一下，形成了六十四卦，每卦六爻，一共三百八十四爻。

爻分阴阳，阳爻性属阳刚，阴爻性属阴柔。天下之大，无奇不有。千奇百怪，皆出此处。

\(mzf\)研究透彻了易经之后，画出了\(n\)个奇怪的图案。他说那是他改进出来的更强大的卜卦体系。

每一个图案有二十行，每一行要么是阴爻\((0)\)，要么是阳爻\((1)\)，作为一个\(OIer\)，我们可以将卦象看成一个个二进制串；

他将\(n\)个图案画在了符纸上，然后进行\(m\)次操作：

操作1：翻转区间\([l,r]\)的图案，比如\((3,1,2,5)\)变成\((5,2,1,3)\)；

操作2：\(mzf\)画地为卦，将\([l,r]\)之间的卦象都异或上新画的那个卦象；

操作3：\(mzf\)会询问机房里的其他人\([l,r]\)之间卦象代表的二进制数权值和。

如果不能正确回答每个操作\(3\)，那么机房风水格局将会改变，我们都将...！

由于\(mzf\)疯狂之下将我们都捆♂绑♂了起来，所以只能求求你来帮我们解决这个问题。

输入格式：

第一行两个正整数：\(n\)，\(m\)（\(n\)为序列长度，\(m\)为操作个数）

第二行\(n\)个正整数：\(a[i]\) (用\(10\)进制数表示每个卦象)\((1<=i<=n)\)

接下来\(m\)行：每行首先一个正整数\(opt\)表示操作类型

1. \(opt==1\)：两个正整数：\(l\)，\(r\)。请翻转区间\([l,r]\)；
2. \(opt==2\)：三个正整数：\(l\)，\(r\)，\(d\)。请将区间\([l,r]\)中的所有卦象都异或卦象\(d\)。\((0<=d<=10^5)\)
3. \(opt==3\)：两个正整数：\(l\)，\(r\)。请查询区间\([l,r]\)的卦象权值和。

输出格式：

对于每个 \(opt==3\) 的情况，输出一行答案。

样例输入：

8 94 6 2 1 7 9 10 21 1 43 1 62 4 5 23 1 62 1 5 83 1 62 5 7 103 4 73 1 10

样例输出：

2929692459

提示与说明：

对于20%的数据，\(n<=1000\)，\(m<=1000\)

对于另外20%的数据，不存在操作\(1\)

对于另外20%的数据，保证\(n\)为\(2\)的次幂，且在操作\(1\)中，保证\(l=i\times(2^j)+1,r=(i+1)\times(2^j)\)，其中\(i\)，\(j\)为任意值

对于100%的数据，\(n<=10^5\)，\(m<=5\times 10^4\)，\(1<=l<=r<=n\)，\(0<=d<2^{20}\)

题解：

方法一：

暴力模拟，期望得分：20。

code:

/*Program from Luvwgyx*/#include
    
     #include
     
      #include
      
       #define ll long longusing namespace std;const int maxn=1010;int n,m,a[maxn],b[maxn];int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}int main(){    n=read();m=read();    for(int i=1;i<=n;i++)a[i]=read();    for(int i=1;i<=m;i++){        int opt=read(),l=read(),r=read(),d;        if(opt==1){            for(int i=l;i<=r;i++)b[i]=a[i];            for(int i=r;i>=l;i--)a[i]=b[l+r-i];            memset(b,0,sizeof(0));                    }else if(opt==2){            d=read();            for(int i=l;i<=r;i++)a[i]^=d;        }else if(opt==3){            ll ret=0;            for(int i=l;i<=r;i++)ret+=a[i];            printf("%lld\n",ret);        }    }    return 0;}
      
     
    

方法二：

不存在操作1，那我们可以考虑用线段树来做。

普通的线段树：期望得分：20。

结合暴力，期望得分：40。

代码就不放了，自己去写一写吧

方法三：

有翻转操作了，但是这个反转的区间有限制，我们会发现这个区间其实就是线段树上的区间的左右端点，我们只需要找到这个区间，然后翻转就好了。

线段树+拆位异或...期望得分：40分

结合暴力，期望得分：60分

线段树内维护权值和以及二进制下数位的值，然后拆位异或，注意一下标记下传之类的就好了。

都是板子，直接上代码看吧...

code:

/*Program from lichenxi*/#include
    
     #include
     
      #include
      
       using namespace std;#define mid ((s[x].l+s[x].r)>>1)#define size (s[x].r-s[x].l+1)int n,m,opt,x,y,c[21],ans[21],f[21];long long d[300001],z,sum,w[21],a[300001];struct oo{int l,r,rev,t[21],ls,rs;long long _XOR;}s[1200001];int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}void gettwo(int *a,long long v){    int now=0;    while(v)    {        if(v&1)a[now]=1;        v>>=1;now++;    }}void update(int x){for(int i=0;i<20;i++)s[x].t[i]=s[s[x].ls].t[i]+s[s[x].rs].t[i];}void build(int x,int l,int r){    s[x].l=l,s[x].r=r;    if(l==r){gettwo(s[x].t,d[l]);return ;}    s[x].ls=x<<1,s[x].rs=x<<1|1;    build(x<<1,l,mid);build(x<<1|1,mid+1,r);    update(x);}void pushrev(int x){    int ca=s[s[x].ls].r-s[s[x].ls].l,ka=s[s[x].rs].r-s[s[x].rs].l;    s[s[x].ls].l=s[x].l;s[s[x].ls].r=s[s[x].ls].l+ca;    s[s[x].rs].l=s[s[x].ls].r+1;s[s[x].rs].r=s[s[x].rs].l+ka;}void pushdown_rev(int x){    s[s[x].ls].rev^=1,s[s[x].rs].rev^=1,s[x].rev^=1;    swap(s[x].ls,s[x].rs);    pushrev(x);}void push_XOR(int *c,int x){for(int i=0;i<20;i++)if(c[i])s[x].t[i]=size-s[x].t[i];}void pushdown_XOR(int x){    s[s[x].ls]._XOR^=s[x]._XOR;s[s[x].rs]._XOR^=s[x]._XOR;    for(int i=0;i<20;i++)f[i]=0;gettwo(f,s[x]._XOR);    push_XOR(f,s[x].ls);push_XOR(f,s[x].rs);    s[x]._XOR=0;}void putrev(int x,int l,int r){    pushrev(x);    if(s[x].rev)pushdown_rev(x);    if(s[x]._XOR)pushdown_XOR(x);    if(s[x].l==l&&s[x].r==r)    {        swap(s[x].ls,s[x].rs);        s[s[x].ls].rev^=1;s[s[x].rs].rev^=1;        int ca=s[s[x].ls].r-s[s[x].ls].l,ka=s[s[x].rs].r-s[s[x].rs].l;        s[s[x].ls].l=s[x].l;s[s[x].ls].r=s[s[x].ls].l+ca;        s[s[x].rs].l=s[s[x].ls].r+1;s[s[x].rs].r=s[s[x].rs].l+ka;        return ;    }    if(l<=mid)putrev(s[x].ls,l,r);    if(r>mid)putrev(s[x].rs,l,r);    update(x);}void change(int x,int l,int r,long long d){    pushrev(x);    if(s[x].rev)pushdown_rev(x);    if(s[x]._XOR)pushdown_XOR(x);    if(l<=s[x].l&&r>=s[x].r){push_XOR(c,x),s[x]._XOR^=d;return ;}    if(l<=mid)change(s[x].ls,l,r,d);    if(r>mid)change(s[x].rs,l,r,d);    update(x);}void get(int x,int l,int r){    pushrev(x);    if(s[x].rev)pushdown_rev(x);    if(s[x]._XOR)pushdown_XOR(x);    if(l<=s[x].l&&r>=s[x].r)    {        for(int i=0;i<20;i++)ans[i]+=s[x].t[i];        return ;    }    if(l<=mid)get(s[x].ls,l,r);    if(r>mid)get(s[x].rs,l,r);    update(x);}int main(){//  freopen("data.in","r",stdin);//  freopen("data.out","w",stdout);    w[0]=1;    for(int i=1;i<22;i++)w[i]=w[i-1]<<1;    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)scanf("%lld",&d[i]);    if(n<=1000&&m<=1000){        while(m--){            int opt=read(),l=read(),r=read(),x;            if(opt==1){                for(int i=l;i<=r;i++)a[i]=d[i];                for(int i=r;i>=l;i--)d[i]=a[l+r-i];                memset(a,0,sizeof(a));            }else if(opt==2){                x=read();                for(int i=l;i<=r;i++)d[i]^=x;            }else if(opt==3){                long long ret=0;                for(int i=l;i<=r;i++)ret+=d[i];                printf("%lld\n",ret);            }        }        return 0;    }    build(1,1,n);    while(m--)    {        scanf("%d%d%d",&opt,&x,&y);        if(opt==1)putrev(1,x,y);        if(opt==2)        {            scanf("%lld",&z);            for(int i=0;i<20;i++)c[i]=0;            gettwo(c,z);change(1,x,y,z);        }        if(opt==3)        {            for(int i=0;i<20;i++)ans[i]=0;get(1,x,y);            sum=0;for(int i=0;i<20;i++)sum+=ans[i]*w[i];            printf("%lld\n",sum);        }    }}
      
     
    

方法四：

当操作\(1\)没有限制后，我们可以想到用平衡树，开\(20\)棵平衡树就可以\(TLE\)了（常数小的说不定卡的过）。每次翻转的时候我们需要翻转\(20\)棵平衡树，这样非常不优。那么我们就把每个数的二进制存到平衡树的节点上，每次异或的时候再拿出来用，翻转操作也只要做一次就好。理论时间复杂度\(O(20\ m\ logn)\)，常数小的基本上可以过

至于有\(dalao\)写的是\(splay\)却\(55\)或\(60\)啥的我也不知道啥情况啊....

我真的没有想卡常啊...可能是我的\(splay\)常数比较小吧...说不定用\(fhq\ treap\)常数小一些，但是我不会写

期望得分：100分。

code:

/*program from Wolfycz*/#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define inf 0x7f7f7f7fusing namespace std;typedef long long ll;typedef unsigned int ui;typedef unsigned long long ull;inline int read(){    int x=0,f=1;char ch=getchar();    for (;ch<'0'||ch>'9';ch=getchar())  if (ch=='-')    f=-1;    for (;ch>='0'&&ch<='9';ch=getchar())    x=(x<<1)+(x<<3)+ch-'0';    return x*f;}inline void print(int x){    if (x>=10)  print(x/10);    putchar(x%10+'0');}const int N=5e5;int v[N+10],g[20]; void Extract(int x,int *cnt){for (int i=0;i<20;i++) cnt[i]=x&1,x>>=1;}struct Splay{    #define ls(x) tree[x][0]    #define rs(x) tree[x][1]    #define T(x) (rs(f[x])==x)    ll sum[N+10];    int tree[N+10][2],f[N+10],size[N+10],cnt[N+10][20],Xor[N+10],val[N+10],A[20];    bool rev[N+10];    int root,len;    void updata(int x){        size[x]=size[ls(x)]+size[rs(x)]+1;        sum[x]=sum[ls(x)]+sum[rs(x)]+val[x];        for (int i=0;i<20;i++)  cnt[x][i]=cnt[ls(x)][i]+cnt[rs(x)][i]+((val[x]>>i)&1);    }    void move(int x){        int fa=f[x],son=tree[x][T(x)^1];        tree[x][T(x)^1]=fa;        tree[fa][T(x)]=son;        if (son)    f[son]=fa;        f[x]=f[fa];        if (f[x])   tree[f[x]][T(fa)]=x;        f[fa]=x;        updata(fa),updata(x);    }    void splay(int x){        while (f[x]){            if (f[f[x]])    T(f[x])==T(x)?move(f[x]):move(x);            move(x);        }        root=x;    }    void Add_rev(int x){        if (!x) return;        swap(ls(x),rs(x));        rev[x]^=1;    }    void Add_xor(int x,int v){        if (!x) return;        Extract(v,A);        ll res=0;        for (int i=0;i<20;i++){            if (A[i])   cnt[x][i]=size[x]-cnt[x][i];            res+=1ll*cnt[x][i]*g[i];        }        sum[x]=res;        val[x]^=v,Xor[x]^=v;    }    void pushdown(int x){        if (rev[x]){            Add_rev(ls(x));            Add_rev(rs(x));            rev[x]=0;        }        if (Xor[x]){            Add_xor(ls(x),Xor[x]);            Add_xor(rs(x),Xor[x]);            Xor[x]=0;        }    }    int find(int x,int i){        pushdown(i);        if (size[ls(i)]+1==x)   return i;        if (x<=size[ls(i)]) return find(x,ls(i));        return find(x-size[ls(i)]-1,rs(i));    }    void reverse(int l,int r){        int x=find(l,root),y=find(r+2,root);        splay(x),splay(y);        if (f[x]!=root) move(x);        Add_rev(rs(x));//      updata(x),updata(y);    }    void _xor(int l,int r,int v){        int x=find(l,root),y=find(r+2,root);        splay(x),splay(y);        if (f[x]!=root) move(x);        Add_xor(rs(x),v);        updata(x),updata(y);    }    ll Query(int l,int r){        int x=find(l,root),y=find(r+2,root);        splay(x),splay(y);        if (f[x]!=root) move(x);        return sum[rs(x)];    }    void build(int fa,int l,int r,int &x){        if (l>r)    return;        int mid=(l+r)>>1;        x=++len,f[x]=fa,val[x]=v[mid];        if (l==r){            size[x]=1,sum[x]=val[x];            Extract(val[x],cnt[x]);            return;        }        build(x,l,mid-1,ls(x));        build(x,mid+1,r,rs(x));        updata(x);    }    void init(int n){        len=2,root=1;        rs(1)=size[1]=2,f[2]=size[2]=1;        build(2,1,n,ls(2));        updata(2),updata(1);    }}Tree;int main(){    g[0]=1;    for (int i=1;i<20;i++)  g[i]=g[i-1]<<1;    int n=read(),m=read();    for (int i=1;i<=n;i++)  v[i]=read();    Tree.init(n);    for (int i=1;i<=m;i++){        int type=read(),l=read(),r=read();        if (type==1)    Tree.reverse(l,r);        if (type==2)    Tree._xor(l,r,read());        if (type==3)    printf("%lld\n",Tree.Query(l,r));    }    return 0;}
        
       
      
     
    

hby与tkw的基情

题目背景：

基情恒久远，一对永流传。

\(hby\)和\(tkw\)是一对好基友，他们经常在一起做♂游♂戏 (/滑稽)。

题目描述：

他们喜欢玩字符串游戏，尤其喜欢玩回文串。每次\(hby\)会给出一个数\(n\)，那么\(tkw\)就需要给出\(Ans=\sum\limits_{i=1}^ni\times s[i]\times[i\%2]\)

其中\(s[i]\)代表长度为\(i\)的数字回文串的个数，最后面是\(bool\)表达式

不过由于\(tkw\)最近学\(ycz\)找妹纸去了，于是他就将这个问题交给了你，如果你不能在\(1s\)内答出来，那么\(hby\)和\(tkw\)的基情将会破裂！（不过那样tkw就可以安心地找妹纸了）

由于答案会非常大，所以你只需要输出答案\(\%10^9+7\)的值即可

输入格式:

第一行一个整数\(T\)。

接下来\(T\)行，每行一个数\(n\)。

输出格式：

共\(T\)行，每行代表一个答案

样例输入：

213

样例输出：

262054

提示与说明：

对于10%的数据：\(n<=5\)

对于另外20%的数据：\(\sum n<=10^7\)

对于另外20%的数据：\(T=1\)

对于100%的数据：\(T<=5\times 10^5,n<=10^9\)

题解：

10%：随便玩玩就好

30%：发现:\(s[i]=s[i-2] * 26\) ，\(s[1]=26\)，递推即可

50%：由于只有一组数据，可以用矩阵快速幂优化以上的递推。

100%：开了\(O2\)说不定矩阵快速幂就过了。。。

然后我们要求的式子其实是

\[\sum\limits_{i=1}^m (2\times i-1)\times 26^i\]

其中\(m=\frac{n+1}{2}\)

这东西显然一个差比数列，裂项相减一下

\[Ans=\sum\limits_{i=1}^m(2\times i-1)\times 26^i\]

\[26Ans=\sum\limits_{i=1}^m(2\times i-1)\times 26^{i+1}\]

\[25Ans=26+(2n-1)\times 26^{n+1}-2\times\sum\limits_{i=1}^m26^i\]

\[25Ans=26+(2n-1)\times 26^{n+1}-2\times\dfrac{26^{n+1}-26}{25}\]

直接快速幂即可

/*program from Wolfycz*/#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define inf 0x7f7f7f7fusing namespace std;typedef long long ll;typedef unsigned int ui;typedef unsigned long long ull;inline int read(){    int x=0,f=1;char ch=getchar();    for (;ch<'0'||ch>'9';ch=getchar())  if (ch=='-')    f=-1;    for (;ch>='0'&&ch<='9';ch=getchar())    x=(x<<1)+(x<<3)+ch-'0';    return x*f;}inline void print(int x){    if (x>=10)  print(x/10);    putchar(x%10+'0');}const int p=1e9+7,inv=2.8e8+2,inv2=5.6e8+5;int mlt(int a,int b){    int res=1;    for (;b;b>>=1,a=1ll*a*a%p)  if (b&1)    res=1ll*res*a%p;    return res;}int main(){    for (int T=read();T;T--){        int n=(read()+1)>>1;        int Ans=(1ll*(26+1ll*(2*n-1)*mlt(26,n+1)%p-2ll*(mlt(26,n+1)-26)%p*inv%p)*inv%p+p)%p;        printf("%d\n",Ans);    }    return 0;}
        
       
      
     
    

抓住czx

题目背景：

蒟蒻\(lty\)出了一道题，但是由于太弱了，所以希望喜欢鸽子的\(czx\)来帮他写一个\(std\)。由于\(czx\)又放鸽子去了，所以没有写\(std\)。蒟蒻\(lty\)觉得受到了学长的鄙视，所以决定去\(czx\)放鸽子的地方找他。

题意简述：

\(czx\)放鸽子的地方是一个公园，公园珂以看作是由\(n\)个点\(m\)条边组成的无向图(保证无自环），\(lty\)将从公园的入口（\(b\)号节点）进去寻找\(czx\)，而\(czx\)会在\(a_i\)个单位时间时变化位置到第\(x\)个节点去，在此之前\(lty\)已经知道了\(czx\)的具体位置和接下来他位置的变化方案，蒟蒻\(lty\)现在想知道他至少需要花多少时间找到\(czx\)。

输入格式：

第一行四个整数\(n\),\(m\),\(b\),\(e\),\(b\)和\(e\)的意义如题面所示。

接下来\(m\)行，每行三个整数\(x,y,z\)，表示\(x\)到\(y\)之间有一条长为\(z\)的边。

第\(m+1\)行一个整数\(T\)，表示\(czx\)位置变化的次数。

接下来\(T\)行，每行两个整数\(a_i\)和\(x\)，表示\(czx\)将在第\(a_i\)个单位时间时移动到第\(x\)个点上去。

输出格式：

一个整数表示最短所需时间。

样例输入：

6 9 1 61 2 11 3 31 4 42 3 23 6 64 5 62 5 93 5 75 6 2310 38 59 2

样例输出：

9

样例解释：

在开始的时候就直接走到\(2\)号节点，然后等到\(czx\)过来。总花费时间\(9\)个单位时间。

数据范围：

对于30%的数据，\(n<=100\),\(m<=1000\),\(T<=100\)

对于另外30%的数据，\(T=0\)

对于100%的数据，\(n<=10^5\),\(m<=5\times10^5\),\(T<=10^5\)

数据结果保证在\(int\)范围内

题解：

关于\(SPFA\)：它还活着（本来想卡的。。。）

30%：瞎\(jb\)弄吧，其实我也不知道这个部分分有啥意义。。。

另外30%：单源最短路板子。（其实是数据太大放不上。。。强行减小数据大小）

100%：首先求一遍单源最短路，如果我们出发去找\(czx\)，但是半路中\(czx\)就\(TP\)（\(MC\)玩家）走了，那么我们不如最开始就找之后的某个点。这样就可以找到一个点，在\(czx\)下次\(TP\)前抓住他即可。

/*program from Wolfycz*/#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define inf 0x7f7f7f7fusing namespace std;typedef long long ll;typedef unsigned int ui;typedef unsigned long long ull;inline int read(){    int x=0,f=1;char ch=getchar();    for (;ch<'0'||ch>'9';ch=getchar())  if (ch=='-')    f=-1;    for (;ch>='0'&&ch<='9';ch=getchar())    x=(x<<1)+(x<<3)+ch-'0';    return x*f;}inline void print(int x){    if (x>=10)  print(x/10);    putchar(x%10+'0');}const int N=1e5,M=1e6;int pre[(M<<1)+10],now[N+10],child[(M<<1)+10],val[(M<<1)+10];int h[N+10],deep[N+10];bool vis[N+10];int n,m,S,tot;struct S1{    int x,T;    void insert(int _x,int _T){x=_x,T=_T;}    bool operator <(const S1 &a)const{return T
         
          N) head=1; int Now=h[head]; for (int p=now[Now],son=child[p];p;p=pre[p],son=child[p]){ if (deep[son]>deep[Now]+val[p]){ deep[son]=deep[Now]+val[p]; if (!vis[son]){ if (++tail>N) tail=1; vis[h[tail]=son]=1; } } } vis[Now]=0; }}int main(){ n=read(),m=read(),S=read(),A[0].insert(read(),0); for (int i=1;i<=m;i++){ int x=read(),y=read(),z=read(); join(x,y,z),join(y,x,z); } SPFA(S); int T=read(); for (int i=1;i<=T;i++){ int x=read(),y=read(); A[i].insert(y,x); } A[++T].insert(0,inf); sort(A,A+1+T); for (int i=0;i<=T;i++){ if (deep[A[i].x]