不分难度.我只是想把一些好玩或者有思维含量的题塞进来.
Inversion Counting
我是不会告诉你其实我是因为这题标签有平衡树才做的.
这题标签有平衡树.但是并不需要平衡树.
这题操作时在反转区间嘛,然后求逆序对.
容易发现,实际上有变化的逆序对只有完全在这个区间内的.换句话说,反转操作对该区间外的答案无影响.
那么这个区间内的逆序对个数是怎么变得捏?
显然,原来的逆序对都会变为正序的;原来的正序对都会变为逆序的.
但是顺着这条路想的话好像最终还是会跑到求区间逆序对上.那这题就没意思了.
所以换种思路.答案只要求输出奇偶,所以从奇偶性方面考虑.
那容易发现区间原正序对个数奇偶性等于现在逆序对个数的奇偶性.
设区间长度为\(len\),则区间内数对总数为\(\frac{len*(len-1)}{2}\).
再设反转后区间逆序对个数为\(num\),则现区间内正序对数量为\(num\).则现区间内逆序对数量为\(\frac{len*(len-1)}{2}-num\).
然后捏,大的来了:
反转前逆序对数量 减去 反转前后逆序对数量差 就是 反转后逆序对数量.所以捏,想判断 反转后逆序对数量的奇偶性 只需判断 反转前后逆序对数量差 的奇偶性.
那这个数量差很显然是\(\frac{len*(len-1)}{2}-num*2\).
\(num*2\)是偶数(显然),那么我们现在只需要判断\(\frac{len*(len-1)}{2}\)的了.
Code
#include<bits/stdc++.h>
namespace Lemuen_Daily
{
#define endl '\n'
#define il inline
#define ll long long
#define ldb long double
#define Croll(i,l,r) for(int i=l;i<=r;++i)
#define Troll(i,l,r) for(int i=l;i>=r;--i)
#define cerr_time std::cerr<<(double)clock()/CLOCKS_PER_SEC
const int maxn=101700;
const ll inf=0x7f7f7f7f7f;
il int read()
{
int f=1,x=0;char w=getchar();
while(w<'0'||w>'9')
{if(w=='-')f=-1;w=getchar();}
while(w>='0'&&w<='9')
{x=(x<<3)+(x<<1)+(w^48);w=getchar();}
return f*x;
}
}using namespace Lemuen_Daily;
int n,m;
int w[maxn];
bool flag;
int num;
namespace Lemuen_BIT
{
int tr[maxn];
int lowbit(int x)
{return x&(-x);}
void add(int x)
{
while(x<=n)
{
tr[x]++;
x+=lowbit(x);
}
}
int query(int x)
{
int ans=0;
while(x)
{
ans+=tr[x];
x-=lowbit(x);
}
return ans;
}
void Get()
{
Troll(i,n,1)
{
num+=query(w[i]);
add(w[i]);
}
}
}
int main()
{
n=read();
Croll(i,1,n)
w[i]=read();
Lemuen_BIT::Get();
flag=!(num%2);
m=read();
while(m--)
{
int l=read(),r=read();
int p=r-l+1;
if((p*(p-1)/2)%2)
flag=!flag;
if(flag)
std::cout<<"even"<<endl;
else
std::cout<<"odd"<<endl;
}
return 0;
}
P9708 [KMOI R1] 集合 First
《关于我最后一个小时才想起来有场比赛没打,最后二十分钟想这道题但是没想出来,然后比赛结束不到十分钟想出来了这回事》
乐子题.
数据范围到 \(1 \times 10^{16}\),\(O(n)\) 都不用想.
试着想想能否单独计算每个数的贡献.
首先我们容易得出一个结论:
因为从大到小排序,所以一个数的排名只与"大于他的数的个数"有关.
因为最后一个数没有大于他的数,所以先考虑前 \(n-1\) 个数.
那么对于每个 \(x\),大于它的数会有 \(n-x\) 个.(后文用 \(m\) 替代 \(n-x\))
这 \(m\) 个数,能组成的集合个数为 \(2^{m}\) 个.
因为要求x的排名,所以考虑这 \(m\) 个数组成的集合的大小.
易得,有 \(2^{m-1}\) 个集合大小为奇数,剩下 \(2^{m-1}\) 个的大小为偶数.
所以我们就能得到一个很抽象但是正确的结论:
这 \(n-1\) 个数,贡献均为 \(0\).
逆天吧?我也觉得逆天.
然后再来单独考虑最后一个数.
我们容易发现,无论怎么组合,他都始终排在第一位,也就是说,他只会产生正贡献.
那么它会产生多少次贡献呢?
因为前 \(n-1\) 个数能组成 \(2^{n-1}\) 个集合,所以为 \(2^{n-1}\) 次.
所以,我们得出总结论:
答案为 \(n \times 2^{n-1}\).
Code
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define endl '\n'
#define int long long
const int mod=911451407;
#define Croll(i,l,r) for(int i=l;i<=r;++i)
#define Troll(i,l,r) for(int i=l;i>=r;--i)
//////////
int n;
int qp(int,int);
//////////
il int read();
//////////
signed main()
{
n=read();
int ans=n%mod*qp(2,n-1)%mod;
cout<<ans<<endl;
return 0;
}
//////////
int qp(int x,int k)
{
int res=1;
while(k)
{
if(k & 1)res=res*x%mod;
x=x*x%mod;k>>=1;
}
return res;
}
//////////
il int read()
{
int f=1,x=0;char w=getchar();
while(w<'0'||w>'9')
{if(w=='-')f=-1;w=getchar();}
while(w>='0'&&w<='9')
{x=(x<<3)+(x<<1)+(w^48);w=getchar();}
return f*x;
}