String
考虑到只有26个字母， 所以区间排序相当于就是把1-26的值从大到小或者从小到大一次区间赋值. 线段树即可. 当然用平衡树套一下的话就没有26这个常数了. 当然有一位神犇Kechan不加读优只用线段树一样跑在0.5s以内.
Kechan的极优代码.
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=1e5+5;
int n,m;
char ch[N];
int getid(char x){return x-'a';}
struct Tree;
void tree_mod(Tree *nd,int lef,int rig,int l,int r,int *tem,int dowhat);
struct Tree{
Tree *lso,*rso;
int cnt[26];
int fla;int sit;
void upd(){
for(int i=0;i<26;i++)
cnt[i]=lso->cnt[i]+rso->cnt[i];
}
void pus(int lef,int rig){
if(fla==-1)return;
int mid=(lef+rig)>>1;
tree_mod(lso,lef,mid,lef,rig,cnt,fla);
tree_mod(rso,mid+1,rig,lef,rig,cnt,fla);
fla=-1;
}
}pool[N<<2],*root,*tail=pool;
Tree *tree_bui(int lef,int rig){
Tree *nd=++tail;
memset(nd->cnt,0,sizeof(nd->cnt));
nd->fla=-1;nd->sit=-1;
if(lef==rig){
nd->cnt[getid(ch[lef-1])]=1;
}else{
int mid=(lef+rig)>>1;
nd->lso=tree_bui(lef,mid);
nd->rso=tree_bui(mid+1,rig);
nd->upd();
}
return nd;
}
void tree_mod(Tree *nd,int lef,int rig,int l,int r,int *tem,int dowhat){
if(l<=lef&&rig<=r){
nd->sit=nd->fla=dowhat;
int tot=0;int las=lef-l;
memset(nd->cnt,0,sizeof(nd->cnt));
if(dowhat==1){
for(int i=0;i<26;i++){
tot+=tem[i];
if(tot>rig-l){
nd->cnt[i]=rig-l-las+1;
break;
}
if(tot>las){
nd->cnt[i]=tot-las;
las=tot;
}
}
}else{
for(int i=25;i>=0;i--){
tot+=tem[i];
if(tot>rig-l){
nd->cnt[i]=rig-l-las+1;
break;
}
if(tot>las){
nd->cnt[i]=tot-las;
las=tot;
}
}
}
}else{
nd->sit=-1;
int mid=(lef+rig)>>1;
if(l<=mid)tree_mod(nd->lso,lef,mid,l,r,tem,dowhat);
if(mid+1<=r)tree_mod(nd->rso,mid+1,rig,l,r,tem,dowhat);
nd->upd();
}
}
void tree_que(Tree *nd,int lef,int rig,int l,int r,int *tem){
if(l<=lef&&rig<=r){
for(int i=0;i<26;i++)
tem[i]+=nd->cnt[i];
}else{
nd->pus(lef,rig);
int mid=(lef+rig)>>1;
if(l<=mid)tree_que(nd->lso,lef,mid,l,r,tem);
if(mid+1<=r)tree_que(nd->rso,mid+1,rig,l,r,tem);
}
}
void tree_pri(Tree *nd,int lef,int rig){
if(nd->sit!=-1){
if(nd->sit==1){
for(int i=0;i<26;i++)
for(int j=1;j<=nd->cnt[i];j++)
printf("%c",i+'a');
}else{
for(int i=25;i>=0;i--)
for(int j=1;j<=nd->cnt[i];j++)
printf("%c",i+'a');
}
}else if(lef==rig){
for(int i=0;i<26;i++)
if(nd->cnt[i]){printf("%c",i+'a');return;}
}else{
nd->pus(lef,rig);
int mid=(lef+rig)>>1;
tree_pri(nd->lso,lef,mid);
tree_pri(nd->rso,mid+1,rig);
}
}
int main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
scanf("%d%d",&n,&m);
scanf("%s",ch);
root=tree_bui(1,n);
while(m--){
int l,r,x;scanf("%d%d%d",&l,&r,&x);
int tem[26];memset(tem,0,sizeof(tem));
tree_que(root,1,n,l,r,tem);
tree_mod(root,1,n,l,r,tem,x);
}
tree_pri(root,1,n);
return 0;
}
/*
5 2
cabcd
1 3 1
3 5 0
*/本蒟蒻的的代码.
#include<stdio.h>
#include<cstring>
const int maxn = 100005;
char s[maxn];
int cnt[27], a[maxn], n, m;
inline const int read(){
register int x = 0;
register char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x;
}
struct node{
node *ls, *rs;
int sum[27], flag, is;
inline void pushdown(int lf, int rg){
if(flag){
int mid = (lf + rg) >> 1;
for(int i = 1; i <= 26; ++i) ls->sum[i] = rs->sum[i] = 0;
ls->sum[flag] = mid - lf + 1, rs->sum[flag] = rg - mid;
ls->flag = rs->flag = flag;
if(lf == mid) ls->is = flag;
if(mid + 1 == rg) rs->is = flag;
flag = 0;
}
}
inline void update(){
for(int i = 1; i <= 26; ++i)
sum[i] = ls->sum[i] + rs->sum[i];
}
}pool[maxn * 4], *tail = pool, *root;
node* build(int lf, int rg){
node *bt = ++tail;
if(lf == rg){
for(int i = 1; i <= 26; ++i) bt->sum[i] = 0;
bt->sum[a[lf]]++; bt->is = a[lf]; bt->flag = 0; return bt;
}
int mid = (lf + rg) >> 1;
bt->ls = build(lf, mid), bt->rs = build(mid + 1, rg);
bt->is = bt->flag = 0; bt->update();
return bt;
}
void query(node* bt, int lf, int rg, int L, int R){
if(L <= lf && rg <= R){
for(int i = 1; i <= 26; ++i) cnt[i] += bt->sum[i];
return;
}
bt->pushdown(lf, rg);
int mid = (lf + rg) >> 1;
if(L <= mid) query(bt->ls, lf, mid, L, R);
if(R > mid) query(bt->rs, mid + 1, rg, L, R);
bt->update();
}
void modify(node* bt, int lf, int rg, int L, int R, int who){
if(L <= lf && rg <= R){
for(int i = 1; i <= 26; ++i) bt->sum[i] = 0;
bt->sum[who] = rg - lf + 1, bt->flag = who;
if(lf == rg) bt->is = who;
return;
}
bt->pushdown(lf, rg);
int mid = (lf + rg) >> 1;
if(L <= mid) modify(bt->ls, lf, mid, L, R, who);
if(R > mid) modify(bt->rs, mid + 1, rg, L, R, who);
bt->update();
}
void query_po(node* bt, int lf, int rg){
if(lf == rg) {printf("%c", bt->is + 'a' - 1); return;}
bt->pushdown(lf, rg);
int mid = (lf + rg) >> 1;
query_po(bt->ls, lf, mid);
query_po(bt->rs, mid + 1, rg);
}
int main(){
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
n = read(), m = read();
scanf("%s", s + 1);
for(register int i = 1; i <= n; ++i) a[i] = s[i] - 'a' + 1;
root = build(1, n);
for(register int i = 1; i <= m; ++i){
int l = read(), r = read(), opt = read();
query(root, 1, n, l, r);
if(!opt){
for(int i = 26; i; --i)
if(cnt[i])
modify(root, 1, n, l, l + cnt[i] - 1, i), l += cnt[i], cnt[i] = 0;
} else {
for(int i = 1; i <= 26; ++i)
if(cnt[i])
modify(root, 1, n, l, l + cnt[i] - 1, i), l += cnt[i], cnt[i] = 0;
}
}
query_po(root, 1, n);
return 0;
}
/*
5 2
cabcd
1 3 1
3 5 0
*/Matrix
这道题题面有问题， 他没有说中间不在给定区间的空位置不能填…比如样例第一行第3个点取0， 1都可以. 方案就不止12种.
这道题dp方程很奇妙， 可以说成基于未来状态上的dp. dp[i][j]表示当前处理到第i列， 有j个 左端点在i之前的 右区间没有处理(所谓处理就是在指那个区间某个位置选一个1)， 所可能的合法方案数. 那么答案就是dp[m][0].
由于是j个右区间没有处理， 那么也就是说右端点在i之前的左区间都要处理. 我们设当前左端点在i这个位置上的右区间有cr个， 右端点在i上的左区间有cl个. 那么如果当前有j个右区间没处理. 那么:
dp[i][j + cr] 就可以从 dp[i -1][j]转移过来. 因为要首先把右端点在i上的左区间给处理了， 那么i之前有i - s[i-1] + j个地方可以选(本身有i 个地方可以选， s[i-1]指的是端点在i-1及之前的所有区间， 我们假设都处理了， 那么每个区间恰好用1个1， 那么可以选的就是i-s[i - 1]， 因为实际上我们有j个没有处理， 那么就是还要加个j. 那么方案数就是i - s[i - 1] + j 里选cl个的排列(顺序不一样是不同的方案).
那么转移方程就是:
dp[i][j + cr[i]] = (dp[i][j + cr[i]] + dp[i - 1][j] * nott % mod) % mod; nott就是上面那个排列.
然后这是cr个右区间都不处理， 要是处理1个的话.
dp[i][j + cr[i] - 1] = (dp[i][j + cr[i] - 1] + dp[i - 1][j] * didd % mod * (j + cr[i]) % mod) % mod;
dp[i][j+cr[i] - 1]之前是有可能更新过的.
解释一下转移， 因为当前处理一个的话因为都是左端点在i之前的， 所以处理一个的话， 就要占一个位置， 所以处理cl的时候就变成i - 1 - s[i-1] + j里选cl个. 然后cr个里面选1个处理就是(j + cr)里选一个的方案.
即可.
Big
对方那个操作就是左移一位， 若x左移一位有1越过2^n就把那个1调到末尾. 所以n = 2时， 3左移1位还是11 – 3. 那么x在异或i个数之后再左移一位其实等价于先左移一位然后将i个数也左移一位， 异或了之后， 再普通的异或后面的即可. 那么预处理出每前i个数左移一位异或再异或后面得到的数即可. 这样有m+1个. 那么就是选一个数让与这m+1个数其中的一个最大异或最小. 建一个tyie树贪心即可， 非常简单的dp.
#include<cstdio>
const int maxn = 4000000;
int n, m, id, root, a[100005], b[100005];
int c[maxn][2], big[maxn], num[maxn];
inline void insert(int &rt, int who, int pos){
if(!rt) rt = ++id;
if(pos == -1) return;
int wanna = (who >> pos) & 1;
insert(c[rt][wanna], who, pos - 1);
}
inline int ca(int x){
return (x << 1) % (1 << n) + (x << 1) / (1 << n);
}
void dfs(int rt, int pos){
if(pos == -1){
big[rt] = 0, num[rt] = 1;
return;
}
if(!c[rt][0]){
dfs(c[rt][1], pos - 1);
num[rt] = num[c[rt][1]];
big[rt] = big[c[rt][1]] + (1 << pos);
return;
}
if(!c[rt][1]){
dfs(c[rt][0], pos - 1);
num[rt] = num[c[rt][0]];
big[rt] = big[c[rt][0]] + (1 << pos);
return;
}
dfs(c[rt][0], pos - 1), dfs(c[rt][1], pos - 1);
if(big[c[rt][1]] > big[c[rt][0]])
big[rt] = big[c[rt][1]], num[rt] = num[c[rt][1]];
else if(big[c[rt][0]] > big[c[rt][1]])
big[rt] = big[c[rt][0]], num[rt] = num[c[rt][0]];
else big[rt] = big[c[rt][0]], num[rt] = num[c[rt][0]] + num[c[rt][1]];
}
int main(){
freopen("big.in", "r", stdin);
freopen("big.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++i)
scanf("%d", &a[i]), b[1] ^= a[i];
for(int i = 1; i <= m; ++i)
b[i + 1] = b[i] ^ a[i] ^ ca(a[i]);
for(int i = 1; i <= m + 1; ++i) insert(root, b[i], n - 1);
dfs(root, n - 1);
printf("%d\n%d\n", big[root], num[root]);
}