逆序对
题目描述
解法
显然不能直接去算逆序对个数，要不然只有操作壹都要用树套树
找规律发现操作壹一定会改变逆序对的奇偶性，这是因为交换相邻的两个数一定会改变原序列的奇偶性，交换 (a_l,a_r) 可以用 (2cdot (r-l)-1) 次相邻交换完成，所以逆序对奇偶性一定改变。
操作二会交换区间的逆序对和非逆序对，设原来逆序对有 (x) 个，交换后逆序对就有 (frac{(r-l)(r-l+1)}{2}-x) 个逆序对，所以我们根本不用管 (x)，而只需要看前面那部分的奇偶性即可。
操作三和操作四相当于把 (a_l/a_r) 通过相邻换位换到另一边去，所以看 ((r-l)cdot k) 的奇偶性即可。
预处理出一开始的逆序对奇偶性就可以做了，时间复杂度 (O(nlog n))
对序逆
题目描述
解法
首先要弄清楚什么情况下能算对，打个程序找规律可以发现排列都能算对，又观察出算错的充要条件是：一个数前面有相同的比他大的数。要证明也不难，我们先考虑把 (1) 选择排序到第一个位置，那么会在 (1) 前面比它大的数中选择一个极长的下降子序列，然后依次换位，发现逆序对只会在换位的数中还有数和他相等的情况下被算小，而且逆序对只会被算小，所以一错就一直错。
现在问题是计数了，出题人给的是 (O(nm)) 的复杂度，不妨考虑 (dp)，我们从 (m) 到 (1) 逐个加入数字，发现如果放了超过 (1) 个位置那么就不能留出空位，也就是说只能是放一段后缀加上任意一个前面位置的形式，而且放完之后没有任何影响。所以设 (f[i][j]) 表示放了 (i) 个数后剩下 (j) 个位置的方案数，转移：
前缀和优化可以做到 (O(n^2))，用这道题的方法可以做到 (O(nlog n))
#include <cstdio>
const int M = 10005;
const int MOD = 998244353;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,w,f[2][M];
signed main()
{
n=read();m=read();
f[0][0]=1;
for(int j=1;j<=m;j++)
{
w^=1;f[w][0]=1;
for(int i=1;i<=n;i++)
f[w][i]=0;
int sum=0;
for(int i=1;i<=n;i++)
{
sum=(sum+1ll*f[w^1][i-1]*i)%MOD;
f[w][i]=(sum+f[w^1][i])%MOD;
}
}
printf("%d
",f[w][n]);
}
未曾设想的道路
题目描述
解法
首先你要会用线段树做历史最大值，其实就是假想一个标记序列，虽然我们不能维护它，但是我们可以维护它的前缀最大值。这道题是类似的，我们维护标记序列的前缀 (k) 大值即可。
具体地，我们维护 (all[i]) 表示线段树节点 (i) 下的历史 (k) 大值，(mx[i]) 表示现在线段树节点下的 (k) 大值，(tag[i]) 表示操作序列的前缀 (k) 大值。首先考虑合并标记，其实就是在原来的标记序列上加上一段，那么把第二段加上标记之后和第一段归并排序即可，(all[i]) 和 (mx[i]) 的上传也是归并的方法，写一个结构题容易完成。
然后考虑下传标记，其实是把 (mx) 经过 (tag) 的影响之后计算到 (all) 里面去。对于 (mx) 里的每一个元素都可以和任意一个 (tag) 里的元素配对，那么我们先把他们和 (tag) 里面最大的配对，然后用优先队列去取最大的配对，再把和下一个 (tag) 的配对插进优先队列里即可，时间复杂度 (O(klog k))
总时间复杂度 (O(mlog ncdot klog k))，瓶颈在于下传标记。
#pragma GCC optimize(2)
#include <cstdio>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
const int M = 100005;
#define pii pair<int,int>
#define make make_pair
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,a[M];
struct zxy
{
int lazy;vector<int> v;
void clear() {lazy=0;v.clear();}
zxy() {clear();}
zxy(int r) {v.resize(1);v[0]=lazy=r;}
void operator += (const zxy &b)
{
vector<int> tmp;
int A=v.size(),B=b.v.size(),i=0,j=0;
tmp.resize(A+B);
while(i!=A && j!=B)
{
if(b.v[j]+lazy>v[i])
tmp[i+j]=b.v[j]+lazy,j++;
else
tmp[i+j]=v[i],i++;
}
for(;i!=A;i++) tmp[i+j]=v[i];
for(;j!=B;j++) tmp[i+j]=b.v[j]+lazy;
v=tmp;lazy+=b.lazy;
if(v.size()>100) v.resize(100);
}
};
//
zxy mx[4*M],all[4*M],tag[4*M];
void up(int i)
{
mx[i]=mx[i<<1];
mx[i]+=mx[i<<1|1];
all[i]=all[i<<1];
all[i]+=all[i<<1|1];
}
void addtag(int x,zxy t)
{
if(t.v.empty()) return ;
priority_queue<pii> q;zxy tmp;
for(int i=0;i<mx[x].v.size();i++)
q.push(make(mx[x].v[i]+t.v[0],0));
while(!q.empty() && tmp.v.size()<100)
{
pii u=q.top();q.pop();
tmp.v.push_back(u.first);
if(u.second<t.v.size()-1)
{
u.first-=t.v[u.second];
u.first+=t.v[++u.second];
q.push(u);
}
}
all[x]+=tmp;
for(int i=0;i<mx[x].v.size();i++)
mx[x].v[i]+=t.lazy;
tag[x]+=t;
}
void down(int i)
{
addtag(i<<1,tag[i]);
addtag(i<<1|1,tag[i]);
tag[i].clear();
}
void build(int i,int l,int r)
{
if(l==r)
{
mx[i]=all[i]=zxy(a[l]);
mx[i].lazy=all[i].lazy=0;
return ;
}
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
up(i);
}
void upd(int i,int l,int r,int L,int R,int v)
{
if(L>r || l>R) return ;
if(L<=l && r<=R)
{
addtag(i,zxy(v));
return ;
}
int mid=(l+r)>>1;down(i);
upd(i<<1,l,mid,L,R,v);
upd(i<<1|1,mid+1,r,L,R,v);
up(i);
}
zxy ask(int i,int l,int r,int L,int R)
{
if(L<=l && r<=R) return all[i];
int mid=(l+r)>>1;down(i);
if(mid>=R) return ask(i<<1,l,mid,L,R);
if(mid<L) return ask(i<<1|1,mid+1,r,L,R);
zxy tmp=ask(i<<1,l,mid,L,R);
tmp+=ask(i<<1|1,mid+1,r,L,R);
return tmp;
}
signed main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
a[i]=read();
build(1,1,n);
while(m--)
{
int op=read(),l=read(),r=read(),k=read();
if(op==0) upd(1,1,n,l,r,k);
else
{
zxy tmp=ask(1,1,n,l,r);
int x=tmp.v.size();x=min(x,k);
printf("%d
",tmp.v[x-1]);
}
}
}