8/3 训练日志 （树状数组+区间覆盖+思维+01字典树）

P5149 会议座位

又看了一遍树状数组，通透了好多。 思路： 1.采用字典树统计记录单词原本的次序，再记录调换后的次序 2.采用树状数组求出逆序对。(本质只求正序对) 大小写敏感，26*2=52个字符，可能有52 个分支，最大5层

#include
#define int long long
#define endl '\n'

using namespace std;
const int N=5e5+5;
const int inf=0x3f3f3f3f;
int n,a[N];
int ch[N][55],idx,cnt[N],tree[N];
char s[N];
void ins(char *s,int rk)
{
    int p=0;
    for(int i=0;s[i];i++)
    {
        int j=s[i]-'a';
        if(!ch[p][j]) ch[p][j]=++idx;
        p=ch[p][j];
    }
    cnt[p]=rk;
}
int query(char *s)
{
    int p=0;
    for(int i=0;s[i];i++)
    {
        int j=s[i]-'a';
        p=ch[p][j];
    }
    return cnt[p];
}
int lowbit(int x){return x&(-x);}
void add(int x,int k)
{
    for(;x=1;x-=lowbit(x))
        tmp+=tree[x];
    return tmp;
}
signed main()
{
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i>s;
        ins(s,i);
    }
    for(int i=1;i>s;
        a[i]=query(s);
    }
    int ans=0;
    for(int i=1;is;int len_s=s.length();
            for(int j=0;jx>>y;
            cout=0;i--)
    {
        int j=x>>i&1;
        if(ch[p][!j])  //走相反位
        {
            res+=1n;
    for(int i=1;i>a[i],ins(a[i]);
    int ans=0;
    for(int i=1;i>i&1;
        if(ch[p][!j])  //走相反位
        {
            res+=1n;
    for(int i=1;i>u>>v>>w;
        add(u,v,w),add(v,u,w);
    }
    dfs(1,0);
    for(int i=1;i