Codeforces Gym 100463 A Crossings逆序数

クロスシング
Time Limit：20 Sec
メモリLimit:256 MB
タイトル接続
http://codeforces.com/gym/100463
Description
Given a permutation P of｛0，1，…，n−1｝，we define the crossing number of it as follows.Write the sequence 0，1，2，.，n−1 from left to to right above the sequence P（0），P（1.stral.line）。and so on.The crossing number of P is the number of pairs of lineas that cross.For example，if n=5 and P=[1,3,0,2,4]then the crossing number of P 3,as shown the figbere.low！“””“””Ŋ“”“””““““””&“\\\\\\\\\\\\\\\25781;;”“""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""ithelement of it is a＿i＋b mod n（with i in the range［0，n−1］）So the example above is specified by Perm(5,2,1)
Input
The e e e are several test cases in the input file.Each test case is specified by three space space-separated numbers n，a，and b on a line.The preme n will be at 1,000.The inputis terminated with a line。
Output
For each case in the input print out the case number follo wed by the crossing number of the permutation.Follows the format in the example out.
Sample Input
5 2 1 19 12 7 0 0
Sample Output
Case 1:3 Case 2:77
HINT
 
題意
n個の数をあげます。i番目の数は(a*i+b)%nに等しいです。それから、逆の順序はいくらですか？
クイズ:
ツリー配列、大胆に
コード

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 1000101
#define mod 10007
#define eps 1e-9
const int inf=0x7fffffff;   //   
/*
inline ll 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 d[maxn];
int c[maxn];
ll n;
int t;
inline 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 lowbit(int x)
{
    return x&-x;
}

void update(int x,int y)
{
    while(x<=n)
    {
        d[x]+=y;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int s=0;
    while(x>0)
    {
        s+=d[x];
        x-=lowbit(x);
    }
    return s;
}
int num[maxn];
ll a,b;
int main()
{
    int t=0;
    while(scanf("%lld%lld%lld",&n,&a,&b)!=EOF)
    {
        t++;
        if(n==0&&a==0&&b==0)
            break;
        memset(d,0,sizeof(d));
        ll ans=0;
        for(int i=0;i<n;i++)
        {
            int x=(a*i+b)%n+1;
            ans+=sum(x-1);
            update(x,1);
        }
        printf("Case %d: %lld
",t,(n-1)*n/2-ans);
    }
}