题目链接：

 

题解：

建立两个树状数组，第一个是，a[1]*n+a[2]*(n-1)....+a[n]*1;第二个是正常的a[1],a[2],a[3]...a[n]

#include "bits/stdc++.h"using namespace std;#define ll long longconst int MAXN=1e5+10;ll sum[MAXN],ans[MAXN];ll num[MAXN];ll n,q;int lowbit(int x){    return x&(-x);}void update(int i , ll x){    ll t=x*(n-i+1);    while(i<=n)    {        sum[i]+=x;        ans[i]+=t;        i+=lowbit(i);    }}ll query1(int x){    ll Sum=0;    while(x)    {        Sum+=sum[x];        x-=lowbit(x);    }    return Sum;}ll query2(int x){    ll Sum=0;    while(x)    {        Sum+=ans[x];        x-=lowbit(x);    }    return Sum;}int main(){    while(scanf("%lld%lld",&n,&q)!=EOF)    {        for(int i=1;i<=n;i++)        {            scanf("%lld",&num[i]);            update(i,num[i]);        }        while(q--)        {            int a,b,c;            scanf("%d",&a);            if(a==1)            {                scanf("%d%d",&b,&c);                ll A1=query1(c)-query1(b-1);                ll A2=query2(c)-query2(b-1);                printf("%lld\n",A2-A1*((n-b+1)-(c-b+1)));            } else            {                scanf("%d%d",&b,&c);                ll k=c-num[b];                num[b]=c;                update(b,k);            }        }    }    return 0;}

　　

 

•  262144K

 

Morgana is learning computer vision, and he likes cats, too. One day he wants to find the cat movement from a cat video. To do this, he extracts cat features in each frame. A cat feature is a two-dimension vector <$x$, $y$>. If x_ixi​= x_jxj​ and y_iyi​ = y_jyj​, then <x_ixi​, y_iyi​> <x_jxj​, y_jyj​> are same features.

So if cat features are moving, we can think the cat is moving. If feature <$a$, $b$> is appeared in continuous frames, it will form features movement. For example, feature <$a$ , $b$ > is appeared in frame $2,3,4,7,8$, then it forms two features movement $2-3-4$ and $7-8$ .

Now given the features in each frames, the number of features may be different, Morgana wants to find the longest features movement.

Input

First line contains one integer $T(1\le T\le 10)$ , giving the test cases.

Then the first line of each cases contains one integer $n$ (number of frames),

In The next $n$ lines, each line contains one integer k_iki​ ( the number of features) and 2k_i2ki​ intergers describe k_iki​features in ith frame.(The first two integers describe the first feature, the $3$rd and $4$th integer describe the second feature, and so on).

In each test case the sum number of features $N$ will satisfy $N\le 100000$ .

Output

For each cases, output one line with one integers represents the longest length of features movement.

样例输入复制

182 1 1 2 22 1 1 1 42 1 1 2 22 2 2 1 4001 1 11 1 1

样例输出复制

3