CF #344 Div. 2

When I am Coding , only God and I know this .
After soon that , only God know this .
                                        ----Someone I don't know

A.Interview

给两个数组，定义函数 $f(x,l,r)=x_l|x_{l+1}|...|x_r$ |的意思是按位或,$x_i$是x数组中第i个数，现在要求

$$\sum_{L=1}^{n}\sum_{R=L}^{n}max(f(a,L,R)+f(b,L,R))$$

$1\leq n \leq 1000$ ， $0 \leq a_i,b_i \leq 10^9$

.
.
.
.
.
.
.
.
.
.
.
因为范围很小，直接枚举就行

//author: CHC
//First Edit Time:	2016-03-05 09:08
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+4;
const int MAXM=1e+5;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
int A[MAXN],B[MAXN];
int main()
{
    int n;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++)scanf("%d",&A[i]);
        for(int i=1;i<=n;i++)scanf("%d",&B[i]);
        int ans=0;
        for(int i=1;i<=n;i++){
            int r1=A[i],r2=B[i];
            for(int j=i;j<=n;j++){
                r1|=A[j];r2|=B[j];
                ans=max(ans,r1+r2);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

扩展

如果$1 \leq n \leq 100000$怎么处理？如果不仅想求得最大值，而且还想求得L,R这两个值(必须满足L尽可能的大并且R尽可能的小)？
直接套用上面那个方法复杂度得爆炸$O(n^2)$
唔。。。做法？把每个数字拆分二进制，然后从高到低枚举处理？
二分，先求得[1,n]的值，先固定左端点二分右端点得$R'$，然后再固定右端点二分左端点得$L'$。得到$[L',R']$？唔。。有时间看下能不能证明。。
如果以上这种方法不行的话试试这样，枚举固定左端点，二分求最小右端点。复杂度大概是这样$O(1log1+2log2+3log3+...+nlogn)$
唔。复杂度太高，还是拆分二进制，枚举二进制从最高位到最低位，找坐标，然后范围就出来了。

B.Print Check

有一个n*m大小的画版(n行m列)，现在有k个以下的操作
$1 r_i a_i$把第$r_i$行染为$a_i$色
$2 c_i a_i$把第$c_i$列染为$a_i$色
经过k个操作后把这个染色版n行m列输出
$1 \leq n,m \leq 5000$ ， $nm\leq 100 000$ ， $1 \leq k \leq 100000$
.
.
.
.
.
.
.
.
.
.
.
.
如果每进行一次操作就完全执行一次，效率实在太低。
用两个哈希数组表示某行是什么颜色或者某列是什么颜色，然后对于每次操作有个权值，输出的时候比较一下权值就知道某行某列是哪个颜色了。

//author: CHC
//First Edit Time:	2016-03-05 09:16
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=10000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
struct Tx {
    int x,val;
}R[MAXN],C[MAXN];
int main()
{
    int n,m,k;
    while(~scanf("%d%d%d",&n,&m,&k)){
        memset(R,0,sizeof(R));
        memset(C,0,sizeof(C));
        int op,t1,x;
        for(int i=1;i<=k;i++)
        {
            scanf("%d%d%d",&op,&t1,&x);
            if(op==1){
                R[t1].x=x;R[t1].val=i;
            }
            else {
                C[t1].x=x;C[t1].val=i;
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<m;j++){
                if(R[i].val>C[j].val)printf("%d ",R[i].x);
                else printf("%d ",C[j].x);
            }
            if(R[i].val>C[m].val)printf("%d\n",R[i].x);
            else printf("%d\n",C[m].x);
        }
    }
    return 0;
}

C.Report

有n个数，m个操作，操作有两种：
$1 r_i$ 把这个数组的$[1,r_i]$区间按非递减排序
$2 r_i$ 把这个数组的$[1,r_i]$区间按非递增排序
$1 \leq n,m \leq 200000$ ， 这n个数$a_i$的范围$|a_i| \leq 10^9$
.
.
.
.
.
.
.
.
.
.
.
如果按照题意所叙述的来操作，每次操作来次排序。。复杂度要爆表了。。$O(mnlogn)$，明显不可行也不能采取。
求一个特殊的子序列，在开始到某次操作的区间，只需要考虑最大的$r_i$所进行的排序方式就行，因为在这次操作之前的排序都无意义。
所以。。思路来了。。(我就懒得画流程图了)

第一步
求这么一个特殊的最大子序列:
假设数列长度为100000,有1000个操作
第400号的$r_{400}$最大，说明400之前的操作都是无用功，记录这个操作。然后从第401~1000次操作中找最大的$r_i$,$401 \leq i \leq 1000$，然后依次迭代以上过程，求出这个特殊的子序列。
第二步
将取到的这个特殊子序列去重
因为获得到的这个特殊子序列可能存在某种相同方式的排序
比如获取到的子序列是这个样子的：
升 升 降 降 升 降
10 9 8 6 3 2
将它去重成这样：
升 降 升 降
10 8 3 2
第三步
对于数组重赋权值重排序，模拟操作过程，假设是以上四次操作
1 2 3 4 5 6 7 8 9 10 11
$1:l_1 = 1$ ， $r_1 = 10$ ， $curpos=1$，把1~10都赋值为max,排序方式为升
$2:l_2 = 1$ ， $r_2 = 8$ ， $curpos=8$，把1~8赋值为max-1,排序方式为降
$3:l_3 = 6$ ， $r_3 = 8$ ， $curpos=6$ ，把6~8赋值为max-2,排序方式为升
…

权值的重赋，排序方式可以和权值融在一个int中，占用一个二进制位就行
两颗线段树。。其实第一步可以用st算法
太久没敲算法题了。。犯了好多愚蠢的代码错误。。。

//author: CHC
//First Edit Time:	2016-03-05 09:51
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=200000 + 1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
#define lson L,mid,rt<<1
#define rson mid+1,R,rt<<1|1
struct Tree {
    int v,tpye,pos;
}tr[MAXN<<4];
void pushup(int rt){
    if(tr[rt<<1].v>tr[rt<<1|1].v){
        tr[rt]=tr[rt<<1];
    }
    else {
        tr[rt]=tr[rt<<1|1];
    }
}
struct TT{
    int t,r;
}A[MAXN];
void build(int L,int R,int rt){
    tr[rt].v=tr[rt].tpye=0;
    if(L==R){
        tr[rt].v=A[L].r;
        tr[rt].tpye=A[L].t;
        tr[rt].pos=L;
        return ;
    }
    int mid=(L+R)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
Tree querymaxpos(int L,int R,int rt,int l,int r){
    if(l<=L&&R<=r){
        return tr[rt];
    }
    int mid=(L+R)>>1;
    Tree t1,t2;
    t1.tpye=t2.tpye=0;
    if(l<=mid)t1=querymaxpos(lson,l,r);
    if(r>mid)t2=querymaxpos(rson,l,r);
    pushup(rt);
    if(t1.tpye==0)return t2;
    if(t2.tpye==0)return t1;
    if(t1.v>t2.v)return t1;
    return t2;
}
//区间更新，单点查询
struct Tree2{
    int x,flag,val;
}tr2[MAXN<<4];
void pushdown2(int rt){
    if(tr2[rt].flag){
        tr2[rt<<1]=tr2[rt];
        tr2[rt<<1|1]=tr2[rt];
        tr2[rt].flag=0;
    }
}
void build2(int L,int R,int rt){
    memset(&tr2[rt],0,sizeof(tr2[rt]));
    if(L==R){
        return ;
    }
    int mid=(L+R)>>1;
    build2(lson);build2(rson);
}
void update2(int L,int R,int rt,int l,int r,int val){
    //printf("update2 %d %d %d\n",L,R,val);
    //while(l>r);
    if(l<=L&&R<=r){
        tr2[rt].val=tr2[rt].x=val;
        tr2[rt].flag=1;
        return ;
    }
    pushdown2(rt);
    int mid=(L+R)>>1;
    if(l<=mid)update2(lson,l,r,val);
    if(r>mid)update2(rson,l,r,val);
    return ;
}
int C[MAXN];
void query2(int L,int R,int rt){
    if(L==R){
        C[L]=tr2[rt].x;
        return ;
    }
    pushdown2(rt);
    int mid=(L+R)>>1;
    query2(lson);query2(rson);
}
int n,m;
int B[MAXN];
Tree res[MAXN],res1[MAXN];
//升
int cmp1(int x,int y){
    return x<y;
}
//降
int cmp2(int x,int y){
    return x>y;
}
int (*cmp[2])(int,int)={cmp1,cmp2};
int D[MAXN];
int cmp3(int x,int y){
    int tx=C[x]>>1,ty=C[y]>>1;
    if(tx==ty){
        if(C[x]&1)return B[x]>B[y];
        else return B[x]<B[y];
    }
    else {
        return tx<ty;
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;i++){
            scanf("%d",&B[i]);
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d",&A[i].t,&A[i].r);
        }
        build(1,m,1);
        int tot=0;
        int l=1,r=m;
        while(l<=r){
            Tree mid=querymaxpos(1,m,1,l,r);
            res[tot++]=mid;
            l=mid.pos+1;
        }
        sort(B+1,B+res[0].v+1,cmp[res[0].tpye-1]);
        int tot1=0;
        res1[tot1++]=res[0];
        for(int i=1;i<tot;i++){
            if(res[i].tpye!=res[i-1].tpye)
                res1[tot1++]=res[i];
        }
        int tflag=res1[0].tpye-1;
        int tval=m+5;
        build2(1,res1[0].v,1);
        update2(1,res1[0].v,1,1,res1[0].v,(tval<<1)|tflag);
        l=1,r=res1[0].v;
        int curpos=1;
        for(int i=1;i<tot1;i++){
            if(l==curpos){
                int t=curpos;
                curpos+=res1[i].v-1;
                l=t;r=curpos;
            }
            else if(r==curpos){
                int t=curpos;
                curpos-=res1[i].v-1;
                l=curpos;r=t;
            }
            tflag=!tflag;
            --tval;
            update2(1,res1[0].v,1,l,r,(tval<<1)|tflag);
        }
        for(int i=1;i<=n;i++)D[i]=i;
        query2(1,res1[0].v,1);
        sort(D+1,D+1+res1[0].v,cmp3);
        for(int i=1;i<n;i++)printf("%d ",B[D[i]]);
        printf("%d\n",B[D[n]]);
    }
    return 0;
}
/*
#1 把C数组和D数组搞混淆了
#2 把tr数组和tr2数组搞混淆了
#3 if(l==curpos) 和 if(r==curpos)分开判断 这是错的，加个else
#4 去重遍历的上限变量名打错，m->tot
#5 去重代码变量名写错
 * */

D. Messenger

有个很长很长的字符串。为了简便，把它缩写成这这种格式。。
3-a 2-b 4-c 3-a 2-c
这个代表的字符串为aaabbccccaaacc
给两个字符串t和s，求s在t中出现的次数。
t和s有n和m部分，$1\leq n,m \leq 200000$，字符都为小写字符
比如下面两个样例：

输入
6 1
3-a 6-b 7-a 4-c 8-e 2-a
3-a
输出
6
s:aaa
t:aaabbbbbbaaaaaaacccceeeeeeeeaa
字符串s在字符串t中出现了三次

输入
5 3
3-a 2-b 4-c 3-a 2-c
2-a 2-b 1-c
输出
1
s:aabbc
t:aaabbccccaaacc
字符串s在字符串t中出现了一次

.
.
.
.
.
.
.
.
.
.
.
.
。。把相邻相同格式的给合并，然后对于字符串s特殊考虑
如果只有一部分，两部分，大于两部分的情况。
对于大于两部分的情况，除去头和尾选择中间部分，找匹配中间部分的在t字符串的起点坐标，然后对比s的头部和尾部。。
kmp可以搞。。